题意

给出n个长度为20的二进制数和数字k，每次询问给出一个二进制数，问从n个数中挑k个数（不能重复）的按位或能包含询问的组合有多少个。数字均小于等于5E5，1s。

思考

强行算出2^20个答案，再O(1)询问。

可知按位或的FWT能够将两个数组融合成新的数组。假设F_k表示挑出k个数字能组成的所有可能的桶，A为原始的桶数组，可知F_k[i]=(F_k-1 或运算FWT A)[i]-(k-1)F_k-1[i]，后面减法的目的是减去数被重复选择的部分。

再观察FWT其实是线性变换，因此F_k[i]可以预先乘上k方便下一次计算。因此最开始只要乘上某个组合数即可。

最后根据按位与FWT可得到所有的答案。总复杂度O(nlogn)。

代码

 #pragma GCC optimize 2

 #include<bits/stdc++.h>

 #define mod 1000000007

 using namespace std;

 typedef long long int ll;

 const int maxn=1E6+5E5+;

 const int LEN=;

 const int G=<<LEN;

 ll n,k,m,a[maxn],b[maxn],c[maxn],d[maxn];

 ll fac[maxn],inv[maxn];

 string str;

 inline int get(string str)

 {

     int sum=;

     for(int i=;i<LEN;++i)

         sum=sum*+str[i]-'';

     return sum;

 }

 ll qpow(ll x,ll y)

 {

     ll ans=,base=x;

     while(y)

     {

         if(y&)

             ans=ans*base%mod;

         base=base*base%mod;

         y>>=;

     }

     return ans;

 }

 void init()

 {

     fac[]=;

     for(int i=;i<=;++i)

         fac[i]=fac[i-]*i%mod;

     inv[]=qpow(fac[],mod-);

     for(int i=-;i>=;--i)

         inv[i]=inv[i+]*(i+)%mod;

 }

 void FWT(ll*A,int t1,int t2)

 {

     for(int len=;len<=G;len<<=)

         for(int i=;i<G/len;++i)

             for(int j=;j<len/;++j)

             {

                 ll a=A[i*len+j],b=A[i*len+j+len/];

                 A[i*len+j]=(a+b*t1)%mod;

                 A[i*len+j+len/]=(b+a*t2)%mod;

             }

 }

 template<class T>void copy(T*a,T*b,int x)

 {

     for(int i=;i<x;++i)

         a[i]=b[i];

 }

 int main()

 {

     ios::sync_with_stdio(false);

     init();

     cin>>n>>k>>m;

     for(int i=;i<=n;++i)

     {

         cin>>str;

         ++a[get(str)];

     }

     copy(c,a,G);

     FWT(a,,);

     for(int i=;i<G;++i)

     {

         if(a[i]>=k)

             a[i]=fac[a[i]]*inv[a[i]-k]%mod;

         else

             a[i]=;

     }

     FWT(a,,-);

     /*

     for(int i=2;i<=k;++i)

     {

         copy(d,a,G);

         FWT(a,0,1);

         copy(b,c,G);

         FWT(b,0,1);

         for(int j=0;j<G;++j)

             a[j]=a[j]*b[j]%mod;

         FWT(a,0,-1);

         for(int j=0;j<G;++j)

             a[j]=(a[j]-d[j]*(i-1)+mod)%mod;

     }

     */

     FWT(a,,);

     while(m--)

     {

         cin>>str;

         cout<<a[get(str)]*inv[k]%mod<<endl;

     }

     return ;

 }

巴特西

[集训]FWT基础练习题

题意

思考

代码

最新文章

热门文章