すごい難しいわけではないけど、妙にAC数が少ない。
https://yukicoder.me/problems/no/1923
問題
整数N,M,Kが与えられる。
Dを小さい方からK個の整数の積とする。
以下の条件を満たす(N+1)要素の正整数列Aは何通りか。
- A[0]=D
- 正整数iに対し、A[i]はA[0]*A[1]*A[2]*...*A[i-1]の約数である。
- A[1]*A[2]*...*A[N]の約数の個数はM個以下である。
解法
ある1つの素数pについて、Aのうち(A[0]以外で)pを約数に持つものについて、要素数と次数の総和をDPで数え上げよう。
続けて、A[1]...A[N]の積の素因数は高々O(logM)なので、素因数の個数を総当たりし、上記DPの結果を用いて、約数の個数がM個以下になるようなケースを数え上げる。
int N,M,K; ll dp[2020][2020]; ll dp2[2020]; ll dp3[14][2020]; const ll mo=998244353; ll modpow(ll a, ll n=mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll comb(ll P_,ll Q_) { if(P_<0 || Q_<0 || Q_>P_) return 0; ll p=1,q=1; Q_=min(Q_,P_-Q_); for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--; return p*modpow(q,mo-2)%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; dp[0][1]=1; dp[0][2]=mo-1; FOR(i,2002) { ll c=comb(N,i); for(x=1;x<=2000;x++) { (dp[i][x]+=dp[i][x-1])%=mo; dp[i+1][x+1]+=dp[i][x]; dp[i+1][min(2001,2*x+1)]+=mo-dp[i][x]; (dp2[x-1]+=dp[i][x]*c)%=mo; } } ll ret=0; dp3[0][1]=1; FOR(i,13) { ll c=comb(K,i); for(x=1;x<=M;x++) { (ret+=dp3[i][x]*c)%=mo; for(y=2;x*y<=M;y++) { (dp3[i+1][x*y]+=dp3[i][x]*dp2[y-1])%=mo; } } } cout<<ret<<endl; }
まとめ
時々難易度とAC数って反比例しないことがあるよね。