計算量を落とすのが難しい。
https://codeforces.com/contest/1954/problem/F
問題
2つの文字列a,bが等しいとは、rotateすると両者を一致させられることを意味する。
整数N,C,Kが与えられる。
文字列Sは、C個の'1'の後に(N-C)個の'0'が付いたN文字の文字列とする。
SのうちK箇所まで0を1に反転できるとき、uniqueな文字列は何通りか。
解法
文字列Tに対し等しい文字列の個数は、Burnsideの補題より、i文字rotateして変わらない文字数をf(i)とするとf(1)~f(N)の平均値となる。
gcd(i,N)=gcd(j,N)ならばf(i)=f(j)なので、以後Nの約数gに対し、条件を満たす0/1の配置方法を数え上げていく。
愚直にやるとO(N^3 d(N))かかるが、うまく状態をまとめるとO(N^2 d(N))になる。
int N,C,K; const ll mo=1000000007; int cnt[3030]; ll dp[3030][3030]; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>C>>K; for(i=1;i<=N;i++) cnt[__gcd(i,N)]++; dp[0][0]=1; FOR(i,N+1) { ll sum[6060]={}; FOR(j,N+1) { sum[j+1]+=dp[i][j]; sum[j+C+1]+=mo-dp[i][j]; if(j) sum[j]+=sum[j-1]; sum[j]%=mo; dp[i+1][j]=sum[j]; } } ll ret=0; for(i=1;i<=N;i++) if(cnt[i]) { if(C>=i) { if(C+K==N) ret+=cnt[i]; continue; } int one=(C+K)*i/N; int zero=i-one; ll all=0,bad=0; for(j=0;j<=one;j++) (all+=comb(i,j))%=mo; /* for(int p=0;p<=C-1;p++) for(int s=0;s<=C-p-1;s++) { for(int z=max(1,zero-1);z<=i-p-s-1;z++) { bad+=dp[z][i-p-s-1]; } }*/ for(int ps=0;ps<=C-1;ps++) { for(int z=max(1,zero-1);z<=i-ps-1;z++) { (bad+=dp[z][i-ps-1]*(ps+1))%=mo; } } all=(all-bad%mo+mo)%mo; (ret+=cnt[i]*all)%=mo; } cout<<ret*modpow(N)%mo<<endl; }
まとめ
シンプルな問題設定ながら、式変形がかなりしんどい。