SRM 518 1000pts NIM

description

求符合以下条件的序列个数:(向1e9+7取模)

  1. 长度为K
  2. 每个元素大小不超过L
  3. 每个元素都是质数
  4. 所有元素的异或和为0 K<=10^9,L<=5*10^4 <!--more-->

TUCAO

这题终于A了……虽然代码不长但是推导和理解还是很难懂的……

SOL

先来看暴力递推:






































上代码!

#include <vector>
#include <string>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <queue>
using namespace std;
const long long Mod=7+(int)1e9;
typedef long long ll;
ll modpow(ll x,ll y){
    ll tmp=1;
    for(;y;y>>=1){
        if((y&1)==1)tmp=tmp*x%Mod;
        x=x*x%Mod;
    }
    return tmp;
}int a[65536],inv2;
void trans(int l,int r)
{
    if(r-l==1)return;
    int len=(r-l)/2,start=l+len;
    trans(l,start);trans(start,r);
    for(int i=l;i< start;i++)
    {
        int x1=(a[i]-a[i+len]+Mod)%Mod,x2=(a[i]+a[i+len])%Mod;
        a[i]=x1;
        a[i+len]=x2;
    }
}void reverseT(int l,int r){
    if(r-l==1)return;
    int len=(r-l)/2,start=l+len;
    for(int i=l;i< start;i++)
    {
        ll x1=a[i],x2=a[i+len];
        a[i]=(x1+x2)*inv2%Mod;
        a[i+len]=(x2-x1+Mod)*inv2%Mod;
    }reverseT(l,start);reverseT(start,r);
}
class Nim
{
public:
    int count(int K, int L)
    {
        inv2=modpow(2,Mod-2);
        int res = 0;
        memset(a,0,sizeof(a));
        for(int i=2;i<=L;i++)
            if(!a[i]){
                for(int j=i+i;j<=L;j+=i)
                    a[j]=1;
            }
        for(int i=2;i<=L;i++)a[i]^=1;
        int right=1;
        while(right<=L)right<<=1;
        trans(0,right);
        for(int i=0;i< right;i++)
            a[i]=modpow(a[i],K);
        reverseT(0,right);
        res=a[0];
        return res;
    }
};

Comments

comments powered by Disqus