第5回 ドワンゴからの挑戦状 予選 : E - Cyclic GCDs

うーん、これは思いつく気がしない。
https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_e

問題

N羽のニワトリがいる。
それぞれの大きさはA[i]である。

ニワトリどうしが手をつなぎ、いくつかの輪を作る。
1羽で輪を作っても構わない。

輪の作り方の美しさとは、各輪の最小の大きさのニワトリの積とする。
輪がr個できるような輪の作り方全通りに対し、美しさの総和をS(r)とする。
GCD(S(1),S(2),...,S(N))を求めよ。

解法

ニワトリを昇順にソートして、挿入DPすることを考える。
(0-originで)i番目のニワトリを輪に加えるとき、

• 既存の輪のどこかに加える場合、その組み合わせはi通り、よって美しさにはi倍寄与する
• 新規に輪を作る場合、和の美しさの定義より美しさにi倍寄与する

こう考えると、多項式f(t) := (A[0]+0)*(A[1]+1)*...*(A[N-1]+N-1)を考えると、S(r)はf(t)のt^rの係数に相当することになる。
ここで、詳細はEditorialを参照して頂くとして、多項式Pの係数の次数のGCDをg(P)とすると、g(PQ)=g(P)g(Q)となる。
よって、求める解はGCD(A[0]+0,...,A[N-1]+N-1)と非常に単純な式になる。

int N;
int A[101010];
ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	ll ret=1;
	FOR(i,N) ret=ret*__gcd(A[i],i)%mo;
	cout<<ret<<endl;
}

まとめ

最後の式変形は普通思いつくのかな…？