# command_block 的博客

### [数学记录]CF449D Jzzhu and Numbers

posted on 2019-08-09 14:51:32 | under 记录 |

$DWT(F_k)[i]=c(i,lim)+c(i,a[k])$

$S[k]=\prod\limits_{i=1}^nc(k,lim)+c(k,a[i])$

$\rm and$ 卷积的 $FWT$ 就能干这事。

$FWT(G)[i]=\sum\limits_{j=0}^{lim}c(i,j)G[j]=\sum\limits_{j=0}^{lim}c(i,j)\sum\limits_{k=0}^{n}[a[k]=j]=\sum\limits_{k=0}^{n}c(i,a[k])$

#include<algorithm>
#include<cstdio>
#define Maxn 1050000
#define mod 1000000007
#define ll long long
using namespace std;
{
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
ll powM(ll a,ll t=mod-2)
{
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int n,maxx,lim=1<<20;
ll S[Maxn];
void DWT(ll *a)
{
for (int len=1;len<lim;len<<=1)
for (int p=0;p<lim;p+=len+len)
for (int i=p;i<p+len;i++)
a[i]=(a[i]+a[i+len])%mod;
}
void IDWT(ll *a)
{
for (int len=1;len<lim;len<<=1)
for (int p=0;p<lim;p+=len+len)
for (int i=p;i<p+len;i++)
a[i]=(a[i]-a[i+len])%mod;
}
int main()
{
}