AtCoder ABC #212 : H - Nim Counting

ABCにしては難しくない？
https://atcoder.jp/contests/abc212/tasks/abc212_h

問題

正整数Nと、K要素の異なる正整数列Aが与えられる。

数列Bを以下のように生成する。

• 要素数Mは、1以上N以下
• 各要素は、Aのうちいずれかを取る

Bの取り方はK+K^2+...+K^N通りある。
この数列でNimを行うとき、先手必勝なのは何通りか。

解法

数列Cを、

• xがAに含まれるならC[x]=1
• xがAに含まれないならC[x]=0

として考える。

2つの数列X,Yの畳み込みZ=X*Yをとして定義する。
すると、解はC,C^2,C^3,....,C^Nにおける、0以外の要素の和となる。
ただ、具体的にCをN通り列挙すると間に合わない。

そこでアダマール変換を用いる。
Cをアダマール変換したのち、各要素を1乗～N乗の総和で置き換えよう。
そして逆変換をするとC+C^2+C^3+....+C^Nで構築される数列が手に入る。

int N,K;
vector<ll> V(1<<16);

ll mo=998244353;
vector<ll> DWTxor(vector<ll> v) {
	int n=v.size(),i,j,m,b;
	for(b=1;b<n;b*=2) {
		for(i=0;i<n;i+=2*b) FOR(j,b) {
			ll x=v[i+j],y=v[i+j+b];
			v[i+j]=(x+y)%mo;
			v[i+j+b]=(x-y+mo)%mo;
		}
	}
	return v;
}

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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K) {
		cin>>x;
		V[x]=1;
	}
	V=DWTxor(V);
	FOR(i,1<<16) {
		if(V[i]==0) V[i]=0;
		else if(V[i]==1) V[i]=N;
		else {
			ll a=(modpow(V[i],N)-1)*V[i]%mo;
			V[i]=a*modpow(V[i]-1)%mo;
		}
	}
	V=DWTxor(V);
	ll ret=0;
	FOR(i,1<<16) if(i) ret+=V[i];
	ret=ret%mo*modpow(1<<16)%mo;
	cout<<ret<<endl;
	
	
}

まとめ

アダマール変換自体は過去にも使ってたけど…。
変換後に要素毎に等比数列の和を取ればいいっての、とっさに理解できないなぁ。