yukicoder : No.2318 Phys Bone Maker

これは割と典型か。
https://yukicoder.me/problems/no/2318

問題

整数Nが与えられる。
以下を満たす整数列Aは何通りか。
Aのprefix LCMをXとしたとき、Xは1に始まりNに終わるdistinctな整数列となる。

解法

dp(n) := Aの先頭何要素か決めたとき、prefix LCMが1に始まりnに終わるdistinctな整数列となる組み合わせ
としたとき、dp(1)=1から初めてdp(N)を求めればよい。
また、考えるべきnはNの約数だけでよい。

dp(x)となる数列Aに1要素加えてdp(y)となる遷移を考える。
xとyを素因数分解したとき、素因数pに対する次数をそれぞれx', y'とする。

• x'＞y'の時、Aの末尾に加える素因数pに対する次数は0択
• x'＜y'の時、Aの末尾に加える素因数pに対する次数はy' 1択
• x'=y'の時、Aの末尾に加える素因数pに対する次数は0～y'の(y'+1)択

なので、素因数pごとに上記分類を考えると、dp(x)→dp(y)に遷移できる値の個数が計算できる。

ll N;
int M;
const ll mo=998244353;
ll dp[7020];
vector<ll> P;
vector<int> Q[7020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> D;
	for(ll a=1;a*a<=N;a++) if(N%a==0) {
		D.push_back(a);
		if(a*a!=N) D.push_back(N/a);
	}
	ll a=N;
	for(x=2;1LL*x*x<=a;x++) if(a%x==0) {
		P.push_back(x);
		while(a%x==0) a/=x;
	}
	if(a>1) P.push_back(a);
	
	sort(ALL(D));
	M=D.size();
	dp[0]=1;
	FOR(y,M) {
		ll a=D[y];
		FOR(i,P.size()) {
			x=0;
			while(a%P[i]==0) x++,a/=P[i];
			Q[y].push_back(x);
		}
		
		FOR(x,y) if(D[y]%D[x]==0) {
			ll pat=1;
			FOR(i,P.size()) {
				if(Q[x][i]==Q[y][i]) pat=pat*(Q[x][i]+1)%mo;
			}
			(dp[y]+=dp[x]*pat)%=mo;
		}
	}
	cout<<dp[M-1]<<endl;
	
	
}

まとめ

素因数分解なしにさっくりできないかな…と横着してしまった。