Div2 Hardも挑戦。
Div1 Mediumとは別だけど、これはこれで面白い問題。
今回はDiv1 Mediumの方が難しいかな。
http://community.topcoder.com/stat?c=problem_statement&pm=12274
数Nが与えられ、H個の数列を作る。数列の各要素は前の数の約数でなくてはいけない。
このような数列の取り方を列挙する。
まず、数Nを素因数分解して行く。
各素因数の次数がCの時、その素因数で割る位置の取り方はなので、これを掛け合わせていく。
Hは10^9とかなり大きいが、Cは=30なので、1~30のmod 1000000009における逆元を取っておけばすんなり計算できる。
int np; ll prime[100000]; const int prime_max = 1000001; void cprime() { int i,j; char p[prime_max]; np=0; ZERO(p); for(i=2;i<prime_max;i++) { if(p[i]) continue; prime[np++]=i; for(j=i*2;j<prime_max;j+=i) p[j]=1; } } ll mod=1000000009; ll rev(ll num) { ll pw = mod-2; ll ret = 1; for(ll i = 30; i >= 0; i--) { ret = (ret*ret)%mod; if((pw>>i)&1) ret = (ret*num)%mod; } return ret; } ll combi(ll N_, ll C_) { const int num=100; static ll rm[num+1]; int i; ll res=1; if(rm[1]==0) for(i=1;i<=num;i++) rm[i]=rev(i); assert(C_<num); FOR(i,C_) { res = (res * rm[i+1])%mod; res = (res * (N_-i))%mod; } return res; } class DivisibleSequence { public: int count(int N, int H) { int i; cprime(); ll res=1; if(H==1) return 1; FOR(i,np) { ll tres = 1; int nd=0; while(N%prime[i]==0){ N /= prime[i]; nd++; tres += combi(H+nd-2,nd);} res = (res*tres)%mod; } if(N>1) res = (res*H) % mod; return res; } };
まとめ
はPが大きくても、Qが小さかったりmodがついている場合は逆元を使ってうまく処理できる。
これは以前に練習したことだな。
重複組み合わせと合わせて、勉強の成果が出たね。