Codeforces 1408I - Bitwise Magic（找性质+集合幂级数）

Yet another immortal D1+D2 I %%%%%%

首先直接统计肯定是非常不容易的，不过注意到这个 \(k\) 非常小，因此考虑对这个 \(k\) 做点文章。我们考虑每个数被执行了多少次 \(-1\) 操作，设第 \(i\) 个数被执行了 \(b_i\) 次 \(-1\) 操作，那么最终的结果就是 \((a_1-b_1)\oplus(a_2-b_2)\oplus\cdots\oplus(a_n-b_n)\)。然后就是比较神仙的一步了，注意到这个 \(b_i\) 也是 \(\le k\) 的，也就是说我们感性地理解一下这个 \(a_i-b_i\) 差距应该不是非常大，因此我们考虑将原序列进行一个增量转化，即我们考虑统计 \(ans’_i\) 表示有多少种操作序列，满足 \((a_1\oplus(a_1-b_1))\oplus(a_2\oplus(a_2-b_2))\oplus(a_3\oplus(a_3-b_3))\oplus\cdots\oplus(a_n\oplus(a_n-b_n))=i\)，那么最终真正的 \(ans_i=ans’_{sum\oplus i}·\dfrac{1}{n^k}\)，其中 \(sum=a_1\oplus a_2\oplus\cdots\oplus a_n\)。

为什么我们要做这么一个奇怪的操作呢？是为了接下来更加神仙的操作做铺垫。我们考虑生成函数，由于这里涉及异或和和操作次数两维，因此我们需要二维生成函数，具体来说我们按照 NFLSOJ #1072 的套路，\(x\) 那一维的指数做异或和，\(y\) 那一维的指数做加法卷积，由于操作的本质是排列，因此我们需要 EGF。我们考虑构造生成函数 \(F_i(x,y)=1+\sum\limits_{j=1}^k\dfrac{1}{j!}x^{b_{i,j}}y^j\)，其中 \(b_{i,j}=a_i\oplus(a_i-j)\)，这样我们将所有 \(F_i(x,y)\) 卷起来得到幂级数 \(H(x,y)\)，那么根据 EGF 那一套理论显然有 \(ans’_i=k![x^iy^k]H(x,y)\)。根据子集卷积的方法，我们考虑将每个幂级数写成 \(\sum\limits_{j=0}^{2^c-1}G_j(y)x^j\) 的形式，这样我们定义的幂级数的乘法就可以看成，对两个系数是形式幂级数的集合幂级数做 xor 卷积，这样我们 FWTxor 一下 \(x\) 那一维就独立了，这样我们每一维上的多项式相乘，再 IFWTxor 回去即可得到真正的系数，相信深入了解过集合幂级数的同学们这一步都不难理解。这样我们就得到了跑不过暴力的 \(4^cc^2\) 的做法。

考虑优化，这时候就要用到我们之前说的“神仙的操作了”，由于 \(k\) 很小，我们猜测本质不同的 \(b_{i,j}\) 个数也不多，事实上的确如此。我们记序列 \(d_i=\{i\oplus(i-1),i\oplus(i-2),\cdots,i\oplus(i-k)\}\)，那么有一个结论，本质不同的 \(d_i\) 个数为 \(\mathcal O(ck)\) 级别，打个表可以发现 \(k=c=16\) 时这个数目为 \(192\)。证明大概就你考虑 \(\text{lowbit}(i)\)，如果 \(\text{lowbit}(i)>k\)，那么显然 \(i-1\) 与 \(i-k\) 在 \(\text{lowbit}(i)\) 以上的位都相同，也就是说 \(d_i\) 只与 \(\text{lowbit}(i)\) 有关，只有 \(\mathcal O(c)\) 种取值，否则后 \(\log_2(k)\) 位的取值肯定是影响 \(d_i\) 的值的，这样就有 \(2^{\log_2(k)}=\mathcal O(k)\) 种取值，第 \(\log_2(k)\) 位以上第一个 \(1\) 的位置也对 \(d_i\) 的取值有影响，其他位置都对 \(d_i\) 的取值产生不了任何影响，因此总共只有 \(ck\) 种取值，证毕。

显然对于 \(d_{a_i}=d_{a_j}\) 的两个下标 \(i,j\)，必然也有 \(F_{i}(x,y)=F_j(x,y)\)，因此我们可以统一对所有本质不同的 \(F_i(x,y)\) 算一遍答案。也就是说我们根据 \(d_i\) 将所有数划分成 \(\mathcal O(ck)\) 个等价类，假设有 \(cnt_i\) 个 \(a_j\) 属于第 \(i\) 个等价类，那么答案应乘上 \(G_i(x,y)^{cnt_i}\)，其中 \(G_i(x,y)\) 表示第 \(i\) 个等价类对应的 \(F_i(x,y)\)。至于怎样计算 \(G_i(x,y)\)……大概就对于每一维 FWTxor 一下然后做一遍多项式快速幂再 IFWTxor 回去，多项式快速幂可以通过取 \(\ln\) 再 \(\exp\) 回去的方法，由于这题数据范围很小，NTT 反而比暴力慢，故我们应选择暴力求 \(\ln,\exp\)，此时复杂度大概是 \(2^cck^3=n\log^4n\)，无法通过此题。

考虑优化，注意到在我们对每一位 FWTxor 之后，每一位上的多项式 \([y^j]\) 的系数肯定是 \(\pm\dfrac{1}{y^j}\)，由于 \(k\) 很小，因此 FWTxor 之后每一位的多项式总共只有 \(2^k\) 种可能，是在我们能够接受的，因此我们考虑对全部 \(2^k\) 种多项式预处理它们的 \(\ln\)，这部分复杂度是 \(2^kk^2\) 的，然后对于每一个等价类，我们对每一维调用预处理的 \(\ln\) 值时，不立即 \(\exp\) 回去，而是直接令当前位多项式的 \(\ln\) 加上 \(cnt_i·\ln(G_i(y))\)，最后再统一 \(\exp\) 回去，这样复杂度就降到了 \(2^cc^3=n\log^3n\)。

卡时限过题真 nm 有趣

const int MAXN=16;

const int MAXP=65536;

const int MAXC=192;

const u64 BS=17;

const int INV2=499122177;

const int MOD=998244353;

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,k,c,fac[MAXP+5],ifac[MAXP+5],inv[MAXP+5],a[MAXP+5];

void init_fac(int n){

	for(int i=(fac[0]=ifac[0]=inv[0]=inv[1]=1)+1;i<=n;i++) inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;

}

int b[MAXC+5][MAXN+5],idcnt,cnt[MAXC+5],bel[MAXP+5];

map<u64,int> id;

void FWTxor(int *a,int len,int type){

	for(int i=2;i<=len;i<<=1)

		for(int j=0;j<len;j+=i)

			for(int k=0;k<(i>>1);k++){

				int X=a[j+k],Y=a[(i>>1)+j+k];

				a[j+k]=1ll*type*(X+Y)%MOD;

				a[(i>>1)+j+k]=1ll*type*(X-Y+MOD)%MOD;

			}

}

void getln(int *a,int *b,int len){

	b[0]=0;

	for(int i=1;i<=len;i++){

		b[i]=1ll*a[i]*i%MOD;

		for(int j=1;j<i;j++) b[i]=(b[i]-1ll*j*b[j]%MOD*a[i-j]%MOD+MOD)%MOD;

		b[i]=1ll*b[i]*inv[i]%MOD;

	}

}

int tmp[MAXN+5][MAXP+5],res[MAXP+5];

void getexp(int *a,int *b,int len){

	b[0]=1;

	for(int i=1;i<=len;i++){

		b[i]=0;

		for(int j=1;j<=i;j++) b[i]=(b[i]+1ll*b[i-j]*j%MOD*a[j])%MOD;

		b[i]=1ll*b[i]*inv[i]%MOD;

	}

}

void calc_hash(){

	for(int i=k;i<(1<<c);i++){

		u64 pw=1,hs=0;

		for(int j=1;j<=k;j++){

			pw=pw*BS;hs+=(i^(i-j))*pw;

		} if(!id[hs]){

			id[hs]=++idcnt;

			for(int j=1;j<=k;j++) b[idcnt][j]=i^(i-j);

		} bel[i]=id[hs];

//		printf("%llu\n",hs);

	} for(int i=1;i<=n;i++) cnt[bel[a[i]]]++;

}

int lnb[MAXP+5][MAXN+5],tt[MAXP+5][MAXN+5];

void init_ln(){

	for(int i=0;i<(1<<k);i++){

		static int pl[MAXN+5]={0};

		memset(pl,0,sizeof(pl));pl[0]=1;

		for(int j=1;j<=k;j++) pl[j]=((i>>(j-1)&1)?ifac[j]:(MOD-ifac[j]));

//		printf("f=");for(int j=0;j<=k;j++) printf("%d%c",pl[j]," \n"[j==k]);

		getln(pl,lnb[i],k);

//		printf("ln=");for(int j=0;j<=k;j++) printf("%d%c",lnb[i][j]," \n"[j==k]);

	}

}

void calc_num(){

	for(int i=1;i<=idcnt;i++){

		memset(tmp,0,sizeof(tmp));

		for(int j=1;j<=k;j++) tmp[j][b[i][j]]=1;

		for(int j=1;j<=k;j++) FWTxor(tmp[j],1<<c,1);

//		printf("dealing %d\n",i);

//		for(int j=1;j<=k;j++) for(int l=0;l<(1<<c);l++)

//			printf("%d%c",tmp[j][l]," \n"[l==((1<<c)-1)]);

		for(int j=0;j<(1<<c);j++){

			int msk=0;

			for(int l=1;l<=k;l++)

				if(tmp[l][j]==1) msk|=(1<<l-1);

			for(int l=1;l<=k;l++) tt[j][l]=(tt[j][l]+1ll*lnb[msk][l]*cnt[i])%MOD;

//			printf("%d %d %d\n",i,j,msk);

		} //printf("%d\n",cnt[i]);

	}

}

int main(){

	scanf("%d%d%d",&n,&k,&c);int sm=0;init_fac(MAXP);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sm^=a[i];

	calc_hash();init_ln();calc_num();

	for(int i=0;i<(1<<c);i++){

		static int pl[MAXN+5]={0};

		memset(pl,0,sizeof(pl));

		getexp(tt[i],pl,k);

		res[i]=pl[k];

//		for(int j=0;j<=k;j++) printf("%d%c",tt[i][j]," \n"[j==k]);

//		for(int j=0;j<=k;j++) printf("%d%c",pl[j]," \n"[j==k]);

//		printf("%d\n",res[i]);

	} FWTxor(res,1<<c,INV2);

//	for(int i=0;i<(1<<c);i++) printf("%d%c",res[i]," \n"[i==((1<<c)-1)]);

	int coef=1ll*fac[k]*qpow(qpow(n,MOD-2),k)%MOD;

	for(int i=0;i<(1<<c);i++) printf("%d%c",1ll*coef*res[sm^i]%MOD," \n"[i==((1<<c)-1)]);

	return 0;

}

巴特西

Codeforces 1408I - Bitwise Magic（找性质+集合幂级数）

最新文章

热门文章