[HDU6057]Kanade’s convolution

本文主要是介绍[HDU6057]Kanade’s convolution，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Kanade's convolution

题解

我们要求的式子是 $c_{k}=\sum_{i \& j=k}a_{i \oplus j}\cdot b_{i | j}$ 。

~~长得极其丑陋。。。~~

于是我们考虑将其变形一下，令 $x=i|j \, , \, y=i\oplus j$ ，于是条件 $i\& j= k\Rightarrow x-y= k$ 。因为y有的1的位置x肯定都有，所以 $x-y=k\Rightarrow x\oplus y= k$ 。由于可以构成这样的 $(x,y)$ 数对的 $(i,j)$ 数对总共有 $2^{bit_{n}}$ 个，我们需要在加时乘上一个 $2^{bit_{n}}$ 。并且加上满足条件 $[x\& y=y]$ 。

于是原式就成了

$c_{k}= \sum_{x\oplus y=k} [x\&y=y]2^{bit_{y}}a_{x}b_{y}$ 。看起来好像FWT呀，可是这个条件该怎么做呢？

我们发现由于x，y它们之间的关系并且 $x\oplus y = k$ ，故 $[x\&y=y]\Rightarrow bit_{x}-bit_{y}=bit_{k}$ 。而 $bit_{x}$ 与 $bit_{y}$ 又可以代表它里面1的个数，我们便想到先把 $2^{bit_{y}}$ 加到 $a_{x}$ 中，再用FMT的形式来表示它，设 $a_{bit_{i}}=\left \{ a_{bit{i},i},...\right \}$ ，就成了

$C_{k}=\sum_{i=k}^{n}A_{i}B_{i-k}$ 。于是，就可以用FMT将其卷积后乘出来再卷回去就行了。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<bitset>
#include<set>
using namespace std;
#define MAXN 2000005
typedef long long LL;
typedef pair<int,int> pii;
const LL mo=998244353;
const LL inv2=mo+1LL>>1LL;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
template<typename _T>
void read2(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<1)+(s^48);s=gc();}x*=f;
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
LL n,lim,a[MAXN],b[MAXN],now,Ans,bit[MAXN];
LL f[22][MAXN],g[22][MAXN],ans[22][MAXN];
void FMT(LL *f,LL opt=1LL){for(int k=1;k<lim;k<<=1)for(int i=0;i<lim;i+=(k<<1))for(int j=0;j<k;j++){LL x=f[i+j],y=f[i+j+k];f[i+j]=(x+y)%mo*opt%mo;f[i+j+k]=(x-y+mo)%mo*opt%mo;}
}
void mul(LL *A,LL *F,LL *G){for(int i=0;i<lim;i++)A[i]=(A[i]+F[i]*G[i]%mo)%mo;}
signed main(){read(n);lim=1<<n;for(int i=0;i<lim;i++)read(a[i]),bit[i]=bit[i>>1]+(i&1);for(int i=0;i<lim;i++)read(b[i]);for(int i=0;i<lim;i++)f[bit[i]][i]=a[i]*(1LL<<bit[i])%mo;for(int i=0;i<lim;i++)g[bit[i]][i]=b[i];for(int i=0;i<=n;i++)FMT(f[i]),FMT(g[i]);for(int i=0;i<=n;i++)for(int j=0;j+i<=n;j++)mul(ans[i],f[j],g[i+j]);	for(int i=0;i<=n;i++)FMT(ans[i],inv2);now=1;for(int i=0;i<lim;i++)Ans=(Ans+ans[bit[i]][i]*now)%mo,now=now*1526LL%mo;printf("%lld\n",Ans);return 0;
}
/**/