AtCoder ARC #116 : C - Multiple Sequences

Eまではサクサク解けたので悪くはない結果。
https://atcoder.jp/contests/arc116/tasks/arc116_c

問題

整数N,Mが与えられる。
N要素の正整数列Aで、各要素がM以下であり、A[i+1]がA[i]の倍数であるようなものは何通りあるか。

解法

f(x) := Aの最後の要素がxであるような、条件を満たす数列の数
とするとが解となる。
あとはf(x)をそれぞれ求めよう。
g(x,n) := n要素の数列Bで、最後の要素がxであり、B[i+1]がB[i]の倍数であってかつ各要素が異なる数列の数
とする。
既存の数列の最後に、末尾の(2倍以上で)倍数となる要素を追加することを考えると
g(a*x,n+1) += g(x,n)
とこの値をDPで計算することができる。

Bが定まると、同じ値の集合を持つ数列Aは値が変わる場所が(n-1)箇所あることに着目するとComb(N-1,n-1)で計算できるので、

で計算できる。

今回g(x,n)はDPで解いたけど、素因数分解の結果を使っても求められそうだね。

int N,M;
const ll mo=998244353;

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 pat[202020][100];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	int cnt=0;
	ll ret=0;
	for(i=1;i<=M;i++) {
		pat[i][1]=1;
		for(j=i*2;j<=M;j+=i) {
			for(x=1;x<=99;x++) {
				if(pat[i][x]==0) break;
				(pat[j][x+1]+=pat[i][x])%=mo;
			}
		}
		for(x=1;x<=99;x++) if(pat[i][x]) {
			(ret+=comb(N-1,x-1)*pat[i][x])%=mo;
		}
		
	}
	cout<<ret<<endl;
}

まとめ

計算量が心配だったので、本番一応最大ケースもテストして出した。