Problem Link

题目大意

给定集合 $S$，定义 $f(S)$ 表示将 $S$ 中所有数异或上 $\mathrm{mex}(S)-1$ 后得到的集合。

$q$ 组询问给定 $n,k,p$，求有多少 $S$ 满足：

• $S\subseteq[0,2^k)$ 且 $0\in S,|S|=n$。
• 序列 $S,f(S),f(f(S)),\dots$ 最终收敛于 $S_0$，且 $\mathrm{mex}(S_0)=p$。

数据范围：$k\le 17,n,p\le 2^k,q\le 2\times 10^5$。

思路分析

设 $|S|<2^k$，考虑刻画 $S$ 收敛时的极限 $p$：

• 如果 $[0,2^{k-1})$ 不全在 $S$ 中，那么 $S$ 的极限等于 $S$ 在 $[0,2^{k-1})$ 中的极限。
• 否则 $\mathrm{mex}(S)-1$ 至少是 $2^{k-1}-1$：
  • 如果 $2^{k-1}$ 在 $S$ 中，那么 $\mathrm{mex}(S)-1$ 至少是 $2^{k-1}$，翻转一次后变成 $S$ 在 $[2^{k-1},2^k)$ 中的极限。
  • 否则 $\mathrm{mex}(S)-1=2^{k-1}-1$：
    • 如果 $2^k-1\not\in S$，那么翻转后 $[0,2^{k-1})$ 依然全满，$2^{k-1}$ 依然不属于 $S$，此时极限就是 $2^{k-1}$。
    • 否则翻转后变成 $2^{k-1}\in S$ 的问题，答案是 $S$ 在 $[2^{k-1},2^k)$ 范围内翻转低 $k-1$ 位后的极限。

容易发现此时 $p$ 一定是 $2$ 的某个幂。

考虑 dp 刻画，$f_{i,j,c}$ 表示考虑值域 $[0,2^i)$，极限 $p=2^j$，当前 $|S|=c$ 的集合数。

但我们无法处理翻转后的情况，注意到翻转后我们要处理的子问题就是一个钦定 $2^k-1\not\in S$ 的子问题，其余限制和原问题相同，设对应的方案数为 $g_{i,j,c}$。

边界条件是 $j=i-1$，此时对于所有 $2^{i-1}\le c\le 2^i-2$，有：

$$f_{i,i-1,c}=g_{i,i-1,c}=\binom{2^{i-1}-2}{c-2^{i-1}}$$

考虑一般的情况，先处理第一种情况，即 $[0,2^{i-1})$ 的极限为 $2^j$，$[2^{i-1},2^i)$ 可以任选的情况：

$$\begin{aligned} f_{i,j,c_0+c_1}&\gets \binom{2^{i-1}}{c_1}f_{i-1,j,c_0}\\ g_{i,j,c_0+c_1}&\gets \binom{2^{i-1}-1}{c_1}f_{i-1,j,c_0} \end{aligned}$$

可以用 NTT 优化，容易把对 $f$ 的卷积省掉。

然后考虑剩余后面的情况，注意翻转的情况仅在 $f$ 中考虑：

$$\begin{aligned} f_{i,j,k+2^{i-1}}&\gets f_{i-1,j,k}\\ g_{i,j,k+2^{i-1}}&\gets g_{i-1,j,k}\\ f_{i,j,k+2^{i-1}}&\gets g_{i-1,j,k} \end{aligned}$$

回答时特判 $n=2^k$ 后答案就是 $f_{k,\log_2p,n}$。

时间复杂度 $\mathcal O(k^32^k+q)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int N=1<<18;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,m;
inline void init(ull B) { b=B,m=ull((uLL(1)<<64)/B); }
inline ull mod(ull a) {
	ull q=((uLL(m)*a)>>64),r=a-q*b;
	return r>=b?r-b:r;
}
}
#define o(x) FastMod::mod(x)
int MOD,G;
int rev[N],inv[N],fac[N],ifac[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
	int ret=1;
	for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
	return ret;
}
void poly_init() {
	vector <int> fr;
	for(int i=2,z=MOD-1;i*i<=z;++i) if(z%i==0) fr.push_back(i),fr.push_back(z/i);
	for(G=2;;++G) {
		bool ok=true;
		for(int z:fr) if(ksm(G,z)==1) { ok=false; break; }
		if(ok) break;
	}
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=o(1ll*(MOD-MOD/i)*inv[MOD%i]);
	fac[0]=ifac[0]=1;
	for(int i=1;i<N;++i) fac[i]=o(1ll*fac[i-1]*i),ifac[i]=o(1ll*ifac[i-1]*inv[i]);
	for(int k=1;k<=N;k<<=1) {
		int x=ksm(G,(MOD-1)/k); w[k]=1;
		for(int i=1;i<k;++i) w[i+k]=o(1ll*x*w[i+k-1]);
	}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {
	for(int i=0;i<n;++i) {
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=n>>1;
	}
	for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
	for(int k=2,x,y;k<=n;k<<=1) {
		for(int i=0;i<n;i+=k) {
			for(int j=i;j<i+k/2;++j) {
				x=f[j],y=o(1ll*f[j+k/2]*w[k+j-i]);
				f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
			}
		}
	}
	if(idft) {
		reverse(f+1,f+n);
		for(int i=0,x=ksm(n);i<n;++i) f[i]=o(1ll*f[i]*x);
	}
}
int f[18][18][N],g[18][18][N],a[N],b[N];
int C(int x,int y) { return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
signed main() {
	ios::sync_with_stdio(false);
	cin>>MOD,FastMod::init(MOD),poly_init();
	for(int i=1;i<18;++i) {
		int s=1<<(i-1),len=s<<1;
		memset(a,0,sizeof(int)*len);
		for(int k=0;k<s;++k) a[k]=C(s-1,k);
		ntt(a,0,len);
		for(int j=0;j<i-1;++j) {
			int *F=f[i][j],*G=g[i][j];
			memset(b,0,sizeof(int)*len);
			for(int k=0;k<s;++k) b[k]=f[i-1][j][k];
			ntt(b,0,len);
			for(int k=0;k<len;++k) b[k]=o(1ll*a[k]*b[k]);
			ntt(b,1,len);
			for(int k=0;k<len;++k) add(G[k],b[k]),add(F[k],b[k]),add(F[k+1],b[k]);
			for(int k=0;k<s;++k) add(F[k+s],f[i-1][j][k]),add(F[k+s],g[i-1][j][k]),add(G[k+s],g[i-1][j][k]);
		}
		if(i==1) f[1][0][1]=g[1][0][1]=1;
		else for(int k=0;k<s-1;++k) f[i][i-1][k+s]=g[i][i-1][k+s]=C(s-2,k);
	}
	int T; cin>>T;
	for(int k,n,p;T--;) {
		cin>>k>>n>>p;
		if(n==(1<<k)) cout<<(p==n)<<"\n";
		else cout<<(p==(p&-p)?f[k][__lg(p)][n]:0)<<"\n";
	}
	return 0;
}