全体で15分切ってたので、時間通り出ておきたかった。
https://yukicoder.me/problems/no/890
問題
整数N,Kが与えられる。
円周上等間隔に並んだN個の点のうちK個を選んだ時、回転対称性がある、すなわち360度未満で回転させて元の形状と一致するものは何通りか。
解法
f(x) := 点x個分右に回転させたとき元と同じ形状になるようなKの選び方の組み合わせ
とする。N/xが整数の場合、N/x=Pとする。すなわち、長さxの同じ並びがP回繰り返した形状ということになるので、
f(x) = Comb(N/P, K/P)
となる。
ここで、この形状は長さがxの約数を繰り返した可能性もある。そこで
g(x) := 最少で点x個分右に回転させたとき元と同じ形状になるようなKの選び方の組み合わせ
とするとg(x) = f(x) - sum(g(y)) (yはx未満のyの約数)となる。
よってxの小さい順にg(x)を求め、またxの倍数zに対しf(z)からg(x)を順次引くことでg(x)を確定させていこう。
g(x)の総和が解。
int N,K; ll mo=1000000007; ll comb(ll N_, ll C_) { const int NUM_=1400001; 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 dp[1010101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; for(i=1;i<N;i++) if(N%i==0) { int L=N/i; if(K%L==0) { dp[i]=comb(i,K/L); } } ll ret=0; for(i=1;i<N;i++) if(dp[i]) { ret+=dp[i]; for(j=i*2;j<=N;j+=i) if(N%j==0) (dp[j]+=mo-dp[i])%=mo; } cout<<ret%mo<<endl; }
まとめ
問題文を読んで6や8が問題に関係あるのかと思ってしまった。