Loading...

序列统计

check评论:0 条 remove_red_eye浏览量:316 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-23

求符合以下条件的序列个数
1.长度为K
2.每个元素大小不超过L
3.每个数都是质数
4.所有数异或和为0 

先把$L$以内的质数筛出来,因为$K$个数$xor$为$0$的种类数就是$k$次这个数列异或卷积后首项的系数,所以$FWT$后快速幂就好

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
ll k,l,a[100010];
int prime[25000],cnt,limit=1;
const int mod=1e9+7,inv=5e8+4;
void shai(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!a[i]) 
        {
            prime[++cnt]=i;    
        }
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++)
        {
            a[i*prime[j]]=1;
            if(i%prime[j]==0) 
            {
                break;
            }
        }
    }
    for(int i=2;i<=n;i++) 
    {
        a[i]=a[i]^1LL;
    }
}
void FWT(ll *n,int flag)
{
    for(int mid=1;mid<limit;mid<<=1)
    {
        for(int r=(mid<<1),i=0;i<limit;i+=r)
        {
            for(int k=0;k<mid;k++)
            {
                ll x1=n[i+k],x2=n[i+mid+k];
                n[i+k]=(x1+x2)%mod,n[i+mid+k]=(x1-x2+mod)%mod;
                if(!flag)
                {
                    n[i+k]=n[i+k]*inv%mod,n[i+mid+k]=n[i+mid+k]*inv%mod;
                }
            }
        }
    }
}
ll ksm(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) 
        {
            res=res*a%mod;
        }
        a=a*a%mod,b>>=1;
    }
    return res;
}
int main()
{
    cin>>k>>l;
    shai(l);
    while(limit<l) 
    {
        limit<<=1;
    }
    FWT(a,1);
    for(int i=0;i<limit;i++) 
    {
        a[i]=ksm(a[i],k);
    }
    FWT(a,0);
    cout<<a[0];
} 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名