AtCoder ARC #198 : E - Monotone OR

別解賢いな。
https://atcoder.jp/contests/arc198/tasks/arc198_e

問題

整数Nと、M個の非負整数Sが与えられる。
今変数xの初期値を0とする。
以下の処理をx=2^Nとなるまで繰り返すとき、その手順は何通りか。

• S[i]を1つ選び、x := (x or S[i]) + 1 で更新する

解法

f(L,R)を、x=Lの状態からx=Rの状態に至る手順の数とする。
求めたいのはf(0,2^N)である。

f(L,R)を再帰的に求めよう。

• L+1=Rの場合
  • f(L,R)は、(L or S[i]) = S[i]となるS[i]の数なので、あらかじめ高速ゼータ変換をしておけばf(L,L+1)を高速に求められる。
• L + 2^(d+1) = Rの場合
  • M= L + 2^dとする。再帰的にA=f(L,M)、B=f(M,R)を求めよう。
  • x=Lの状態からx=Mの状態を経由してx=Rとなるのは、A*B通り。
  • x=Lの状態からx=Mの状態を経由せずx=Rとなるのは、途中でS[i]が2^dを含むものを選ぶケースである。
  • ここで、A=f(L,M)とB=f(M,R)の違いは、前者はS[i]=2^dを含むものを選ばない場合で、後者は選んでも選ばなくてもよい場合である。
  • よって、x=Lからx=Mの状態を経由せずx=Rとなる数は、両者の差のB-Aである。
  • なのでf(L,R)=A*B+B-Aと置ける。

int N,M;
const ll mo=998244353;
ll A[(1<<24)+1];

ll dfs(int L,int R) {
	if(L+1==R) return A[L];
	int M=(L+R)/2;
	ll a=dfs(L,M);
	ll b=dfs(M,R);
	return (a*b+b-a+mo)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x;
		A[x]++;
	}
	FOR(i,N) FOR(j,1<<N) if(j&(1<<i)) A[j]+=A[j^(1<<i)];
	cout<<dfs(0,1<<N)<<endl;
	
}

まとめ

この解法思いつかなかった…。