AtCoder ABC #428 (Promotion of AtCoderJobs) : G - Necklace

ポリアか？と思ったら違った。
https://atcoder.jp/contests/abc428/tasks/abc428_g

問題

N種類の宝石があり、それぞれ個数は無限にある。
i番目の宝石の美しさをB[i]とする。
宝石をいくつか円形につなぐことを考える。なお、回転して同じ形状になるものは1つと考える。(反転はしない)

f(x) := 美しさの積がxとなる宝石のつなぎ方の数
としたとき、f(2),f(3),....f(U)を求めよ。

解法

F(m,l) := 回転を無視して、l個の宝石をつないだ時に美しさの積がmとなるような並べ方
とする。B[i]≧2よりlはO(logU)まで考えればよいので、このテーブルはDPで簡単に求められる。

G(m,l) := F(m,l)のうち、最短周期がlであるもの
とする。G(m,l)に対し、G(m,l)/lだけ解f(m)に寄与することになる。

最短周期がlより短いものについて、もしF(m,l)が最短パターンをd回繰り返している場合を考えると

となる。また、

となる。

int N,U;
int B[505050];

const int NUM_=2000003;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];


ll F[505050][22];
const ll mo=998244353;
vector<pair<int,int>> D[505050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;
	
	cin>>N>>U;
	FOR(i,N) {
		cin>>x;
		B[x]++;
	}
	
	for(i=2;i<=U;i++) {
		ll x=i;
		for(j=2;x*i<=U;j++) {
			x*=i;
			D[x].push_back({i,j});
		}
	}
	
	
	F[1][0]=1;
	FOR(l,20) {
		for(j=1;j<=U/2;j++) if(F[j][l]) {
			for(x=2;j*x<=U;x++) (F[j*x][l+1]+=F[j][l]*B[x])%=mo;
		}
	}
	
	for(i=2;i<=U;i++) {
		ll ret=0;
		for(j=1;j<=19;j++) {
			//cout<<i<<" "<<j<<" "<<F[i][j]<<"->";
			FORR2(a,b,D[i]) if(j%b==0) {
				(F[i][j]-=F[a][j/b])%=mo;
				ret+=F[a][j/b]*inv[j/b]%mo;
			}
			F[i][j]=(F[i][j]%mo+mo)%mo;
			ret+=F[i][j]*inv[j]%mo;
			//cout<<F[i][j]<<endl;
		}
		cout<<ret%mo<<" ";
	}
	cout<<endl;
	
	
}

まとめ

Gはまだしも、Fに結構手間取った。