kmjp's blog

競技プログラミング参加記です

yukicoder : No.1923 Divisor Array

すごい難しいわけではないけど、妙に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数って反比例しないことがあるよね。