se3948_30.03.23

题目描述

为了抵御以尼古拉奥尔丁为首的上古龙族的入侵，地球的守护者 Yopilla 集齐了 n n n 种人类文明的本源力量 —— 世界之力。

Yopilla 打算使用若干种技能来对抗尼古拉奥尔丁的进攻。每种技能由若干种世界之力构成。换句话说，一共有 2 n 2 ^ n 2n 种技能，Yopilla 要使用若干种技能来对抗尼古拉奥尔丁。

大战前夕，Yopilla 走在波士顿的街头，突然看见天空中飞过了 4 4 4 只白鸽，他便洞察了战胜尼古拉奥尔丁的秘密：只要他使用的技能中，都含有的世界之力的种类数恰好为 4 4 4 的倍数，他便可以打败敌人。

Yopilla 想知道，他有多少种使用技能的情况，能战胜敌人。请你替 Yopilla 回答这个问题，答案对 998244353 998244353 998244353 取模即可。

题解

好仙的题啊

考虑设交集大小至少为 x x x 的个数为 a x a_x ax​ ，则 a x = ( x n ) ( 2 2 n − x − 1 ) a_x=(_x^n)(2^{2^{n-x}}-1) ax​=(xn​)(22n−x−1)

然后我们考虑构造容斥系数 f x f_x fx​ ，使得 a n s = ∑ x = 0 n f x a x ans=\sum_{x=0}^nf_xa_x ans=∑x=0n​fx​ax​

然后我们考虑到如果交集大小恰好为 x x x 的最终要被算 [ x % 4 = 0 ] [x\%4=0] [x%4=0] 遍，而对于 ≤ x \le x ≤x 的 i i i ，它对于 x x x 的贡献就是 ( i x ) (_i^x) (ix​) ，所以我们要使得 [ x % 4 = 0 ] = ∑ k = 0 x ( k x ) f x [x\%4=0]=\sum_{k=0}^x(_k^x)f_x [x%4=0]=∑k=0x​(kx​)fx​

考虑二项式反演，将式子化为 f x = ∑ k = 0 x ( − 1 ) x − k ( k x ) [ x % 4 = 0 ] f_x=\sum_{k=0}^x(-1)^{x-k}(_k^x)[x\%4=0] fx​=∑k=0x​(−1)x−k(kx​)[x%4=0]

考虑将 [ x % 4 = 0 ] [x\%4=0] [x%4=0] 化开，这时候我们要用到很神奇的东西：单位复数根

记 w m w_m wm​ 表示主 m m m 次单位根，那么根据性质，我们可以得到 [ x % m = 0 ] = ∑ i = 0 m − 1 ( w m x ) i [x\%m=0]=\sum_{i=0}^{m-1}(w_m^x)^i [x%m=0]=∑i=0m−1​(wmx​)i

于是 f x = ∑ k = 0 x ( − 1 ) x − k ( k x ) ∑ i = 0 4 − 1 ( w 4 x ) i f_x=\sum_{k=0}^x(-1)^{x-k}(_k^x)\sum_{i=0}^{4-1}(w_4^x)^i fx​=∑k=0x​(−1)x−k(kx​)∑i=04−1​(w4x​)i

把 i i i 提前，得到 f x = ( − 1 ) x 4 ∑ i = 0 3 ( 1 − w 4 i ) x f_x=\frac{(-1)^x}{4}\sum_{i=0}^{3}(1-w_4^i)^x fx​=4(−1)x​∑i=03​(1−w4i​)x

于是我们可以 O ( n m ) O(nm) O(nm)处理出 f x f_x fx​ ，然后计算答案

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,P=998244353;
int n,jc[N],ny[N],w[4],W[4],f[N],s=1;
int X(int x){ 
return x>=P?x-P:x;}
int C(int x,int y){ 

return 1ll*jc[x]*ny[y]%P*ny[x-y]%P;
}
int K(int x,int y){ 

int z=1;
for (;y;y>>=1,x=1ll*x*x%P)
if (y&1) z=1ll*z*x%P;
return z;
}
int main(){ 

cin>>n;jc[0]=1;
for (int i=1;i<=n;i++)
jc[i]=1ll*i*jc[i-1]%P;
ny[n]=K(jc[n],P-2);
for (int i=n;i;i--)
ny[i-1]=1ll*i*ny[i]%P;
w[0]=1;w[1]=911660635;
for (int i=2;i<4;i++)
w[i]=1ll*w[i-1]*w[1]%P;
for (int i=0;i<4;i++)
W[i]=1,w[i]=X(1+P-w[i]);
for (int i=0,F=1;i<=n;i++,F=P-F){ 

for (int j=0;j<4;j++)
f[i]=X(f[i]+W[j]);
f[i]=748683265ll*F%P*f[i]%P;
for (int j=0;j<4;j++)
W[j]=1ll*W[j]*w[j]%P;
}
for (int i=n,v=2,u;~i;i--)
u=1ll*C(n,i)*X(v-1+P)%P,
s=X(s+1ll*u*f[i]%P),v=1ll*v*v%P;
cout<<s<<endl;return 0;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/184479.html原文链接：https://javaforall.cn