beet's soil

競プロのことなど

AtCoder Regular Contest 067

AtCoder

Eの解説を頑張って書いた。(公式が5行だったため）

【C - Factors of Factorial】

素因数の数を数えて公式にぶち込む。
素因数はたかだかN個しかないので愚直にやればいい。
O(NlogN)っぽい？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD=1000000007LL;
int main(){
  ll n;
  cin>>n;
  ll dp[n+1];
  memset(dp,0,sizeof(dp));
  for(ll i=1;i<=n;i++){
    ll t=i;
    for(ll j=2;j<=n;j++){
      while(t%j==0) {
	dp[j]++;
	t/=j;
      }
    }
  }
  ll ans=1;
  for(ll i=0;i<=n;i++) (ans*=dp[i]+1)%=MOD;
  cout<<ans<<endl;
  return 0;
}
【D - Walk and Teleport】

テレポートするかしないかでDP。
遷移が少ないので貪欲でもいけそう。
O(N)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,a,b;
  cin>>n>>a>>b;
  ll x[n],inf=1LL<<50LL;
  for(ll i=0;i<n;i++) cin>>x[i];
  ll dp[n];
  fill(dp,dp+n,inf);
  dp[0]=0;
  for(ll i=0;i<n-1;i++) dp[i+1]=min(a*(x[i+1]-x[i]),b)+dp[i];
  //for(ll i=0;i<n-1;i++) cout<<dp[i]<<endl;
  cout<<dp[n-1]<<endl;
  return 0;
}
【E - Grouping】

前計算で
facti[k]=(k!)−1(1≦k≦N) と
po[k][p]=((k!)−1)p(1≦k×p≦N)
を求めておきます。

まず、N人の順列は自明にN!通りあります。
これをi人のグループの数がpi(a≦i≦b∧(pi=0∨c≦pi≦d))となるように分けたとすると、求める場合の数は、
N!∏i=ab(i!)pi×pi!
となります。

ここで、
dp[j][i]:=i人未満のグループで全部でj人のグループを作ったときの場合の数
と置けば一応DPができます。

しかし、Nが大きくなるとMODを超えてしまうので、
dp[j][i]:=i人未満のグループで全部でj人のグループを作ったときの場合の数の逆元
のように置き換えます。

a×(b−1+c−1)≡a×b−1+a×c−1のため、あとは愚直に遷移を書けば通ります。


一回の遷移が∑k=1n1k=Nlog⁡Nで、全体でN回あるのでO(N^2logN)。
オーバーフローに気づけないのもったいない。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll extgcd(ll a,ll b,ll& x,ll& y){
  ll d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
ll mod_inverse(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
ll MOD=1000000007LL;

ll dp[1111][1111];
ll fact[1111],facti[1111];
ll po[1111][1111];
int main(){
  ll n,a,b,c,d;
  cin>>n>>a>>b>>c>>d;

  fact[0]=facti[0]=1;
  for(ll i=1;i<=n;i++){
    fact[i]=(fact[i-1]*i)%MOD;
    facti[i]=(facti[i-1]*mod_inverse(i,MOD))%MOD;
    assert((fact[i]*facti[i])%MOD==1);
  }
  
  for(ll i=1;i<=n;i++){
    po[i][0]=1LL;
    for(ll j=1;i*j<=n;j++){
      po[i][j]=((po[i][j-1])*facti[i])%MOD;
    }
  }
  
  dp[0][a]=1;
  for(ll i=a;i<=b;i++){
    for(ll j=0;j<=n;j++){
      if(dp[j][i]==0) continue;
      (dp[j][i+1]+=dp[j][i])%=MOD;
      for(ll k=c;k<=d;k++){
	if(j+i*k>n) break; 
	(dp[j+i*k][i+1]+=((dp[j][i]*po[i][k])%MOD)*facti[k])%=MOD;
      }
    }
  }

  /*//
  for(ll j=0;j<=n;j++)
    for(ll i=a;i<=b+1;i++) 
      cout<<dp[j][i]<<" \n"[i==b+1];
  //*/

  ll ans=1LL;
  for(ll i=1;i<=n;i++) (ans*=i)%=MOD;
  cout<<(ans*dp[n][b+1])%MOD<<endl;
  return 0;
}
【全体】

1880 -> 1908 (+28) highest
Eが時間内に解けたのが嬉しかった。
黄色が近づいてきている…！