HDU
6057
题意
给你两个数组 \(A[0\dotsc 2^m-1]\) 和
\(B[0 \dotsc 2^m-1]\)
你需要计算
\[C[k]=\sum_{i~{\rm and}~j=k}A[i~{\rm
xor}~j]\times B[i~{\rm or}~j]\]
输出 \(\sum_{i=0}^{2^m-1}C[i]\times 1526^i
\bmod 998244353\)
\(m\le 19\)
做法
由于 \(i~{\rm and}~j=k\),所以有
\(i~{\rm or}~j=i~{\rm xor}~j~{\rm
xor}~k\),(\(i~{\rm xor}~j\) 与
\(k\) 无交)
那么可以转化
\[
\begin{align}
C[k]&=\sum_{x~{\rm xor}~y=k}[x~{\rm and}~y=x]\times A[x]\times
B[y]\times 2^{ {\rm popcount}(x)} \\
&=\sum_{x~{\rm xor}~y=k}[{\rm popcount}(y)-{\rm popcount}(x)={\rm
popcount}(k)]\times A[x]\times B[y]\times 2^{ {\rm popcount}(x)}
\end{align}
\]
其中 \({\rm popcount}(x)\) 等于
\(x\) 的二进制表示中 \(1\) 的个数
定义\(a_{i,j}=[{\rm popcount}(j)=i]\times
A[j],b_{i,j}=[{\rm popcount}(j)=i]\times B[j]\)
也就是增加一维集合大小,那么
\[c_{i,k}=\sum_{j=0}^i\sum_{x\ {\rm xor}\
y=k}a_{j,x}\times b_{i-j,y}\times 2^j\]
\(C[i]=c_{ {\rm
popcount}(i),i}\),其他多余的位置是没有意义的
那么我们对每一个 \(a_i,b_i\) 做
FWT,再暴力枚举第一维,加到对应的 \(c_i\) 上
时间复杂度 \(\mathcal O(m^2 \times
2^m)\)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include<cstdio> #include<algorithm> #include<ctype.h> #include<string.h> #include<math.h>
using namespace std; #define ll long long
inline char read() { static const int IN_LEN = 1000000; static char buf[IN_LEN], *s, *t; return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++); } template<class T> inline void read(T &x) { static bool iosig; static char c; for (iosig=false, c=read(); !isdigit(c); c=read()) { if (c == '-') iosig=true; if (c == -1) return; } for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0'); if (iosig) x=-x; }
const int N = 20, M = 1<<19, P = 998244353; int ans, m, cnt[M], a[N][M], b[N][M], c[N][M]; inline int Pow(ll x, int y=P-2){ int ans=1; for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P; return ans; } inline void FWT(int *f, int g){ for(int i=1; i<1<<m; i<<=1) for(int j=0; j<1<<m; j+=i<<1) for(int k=j; k<j+i; ++k){ int x=f[k], y=f[k+i]; f[k]=(x+y)%P, f[k+i]=(x-y+P)%P; } if(g==-1) for(int i=0, I=Pow(1<<m); i<1<<m; ++i) f[i]=(ll)f[i]*I%P; } int main() { read(m); for(int i=1; i<1<<m; ++i) cnt[i]=cnt[i^(i&-i)]+1; for(int i=0; i<1<<m; ++i) read(a[cnt[i]][i]); for(int i=0; i<1<<m; ++i) read(b[cnt[i]][i]); for(int i=0; i<=m; ++i) FWT(a[i], 1), FWT(b[i], 1); for(int i=0, p=1; i<=m; ++i, p<<=1) for(int j=i; j<=m; ++j) for(int k=0; k<1<<m; ++k) c[j-i][k]=(c[j-i][k]+(ll)a[i][k]*b[j][k]%P*p)%P; for(int i=0; i<=m; ++i) FWT(c[i], -1); for(int i=0, k=1; i<1<<m; ++i, k=k*1526ll%P) ans=(ans+(ll)k*c[cnt[i]][i])%P; return printf("%d\n", ans), 0; }
|