yukicoder : No.1304 あなたは基本が何か知っていますか？私は知っています．

今年もAdvent Calendarコン開始。
https://yukicoder.me/problems/no/1304

問題

K要素の整数集合Aが与えられる。
Aに含まれる値からなるN要素の数列Bを考える。

• Bの隣接要素は一致しない
• Bの全要素のxorはX以上Y以下である

ようなBは何通りか。

解法

以下を考える。
dp(n,x,p) := Bのうち先頭n要素目まで決めたとき、そのxorを取った値はxで、最後の要素はpである
dp(0,0,-1)=1から初めて、a∈Aに対し
dp(n+1,x^a,a) += dp(n,x,p) (ただしp!=a)
を求めて行けばよい。これはpに関する累積和を適宜取っていけば、Aの最大値をMとして全体でO(NMK)で行ける。

最後にdp(N,X,*)～dp(N,Y,*)の総和を取ろう。

int N,K,X,Y;
set<int> S;
const ll mo=998244353;

ll from[1024][1024],fs[1024];
ll to[1024][1024];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>X>>Y;
	FOR(i,K) {
		cin>>x;
		S.insert(x);
	}
	FORR(s,S) from[s][s]=1;
	FOR(i,N-1) {
		ZERO(to);
		FOR(j,1024) {
			fs[j]=0;
			FORR(s,S) fs[j]+=from[j][s];
			fs[j]%=mo;
		}
		FOR(j,1024) FORR(s,S) (to[j^s][s]+=fs[j]+mo-from[j][s])%=mo;
		swap(from,to);
	}
	
	ll ret=0;
	FOR(i,1024) if(X<=i&&i<=Y) FORR(s,S) {
		ret+=from[i][s];
	}
	
	cout<<(ret+mo)%mo<<endl;
}

まとめ

K^Nの制限は何だったんだろ。