command_block 的博客

command_block 的博客

[数学记录]CF449D Jzzhu and Numbers

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

题意十分简洁。

套路 $\rm FWT$ 题 ($DP$是啥?我不会)

首先,构造一堆位运算意义下的幂级数进行 $\rm and$ 卷积,最后第 $0$ 项就是答案。

设 $lim=(11111...)_2$ ,即全集。

构造 $F_i[lim]=F_i[a[i]]=1$ ,这样 $\rm and$ 卷积中,若卷到 $lim$ 的意义是不选,卷到 $a[i]$ 的意义是选。

然后 $[x^0]\prod\limits_{i=1}^nF_i(x)$ 就是答案。

直接暴力卷积是 $O(n^2logn)$ 的,不可取。

每个多项式都只有两个非$0$项,我们来寻找一下规律:

设 $c(i,j)$ 为and卷积的变换系数。

则 $FWT(F_k)[i]=\sum\limits_{j=0}^{lim}c(i,j)F_k[j]$

由于只有两个非$0$位,可以写作 :

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

众所周知 $c(i,j)=[i\&j=i]$

设 $S[k]=\prod\limits_{i=1}^nDWT(F_i)[k]$

那么 $IFWT(S)$ 就是我们要求的答案。

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

可以得到 $c(k,lim)=[k\&lim=k]$ ,恒等于$1$。

问题就在于有多少个 $c(k,a[i])$ 为$1$,这样对应的位置就是 $2$ ,知道了之后我们一个快速幂就能求 $S[k]$ 了。

观察可得每个 $a[i]$ 会向是他的子集的 $k$ 贡献。

那么就是对 “$G[a[i]]=a[i]$ 的出现次数” 这个多项式做一个高维前缀和。

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

其实这并非巧合,直接考虑 $FWT(G)$ 的结果 :

$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;
inline int read()
{
  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()
{
  n=read();
  for (int i=1,sav;i<=n;i++){
    S[sav=read()]++;
    maxx=max(maxx,sav);
  }lim=4;
  while(lim<=maxx)lim<<=1;
  DWT(S);
  for (int i=0;i<lim;i++)
    S[i]=powM(2,S[i]);
  IDWT(S);
  printf("%lld",S[0]<0 ? mod+S[0] : S[0]);
  return 0;
}