兔子的晚会 2016Vijos省选集训 day1

兔子的晚会 (xor.c/pas/cpp)
=============================

很久很久之前，兔子王国里居住着一群兔子。每到新年，兔子国王和他的守卫总是去现场参加晚会来欢庆新年。

在新年晚会上，兔子国王和他的守卫们坐在观众席的第一排，兔子国王坐在这排最中间的位置，然后国王两边各坐有恰好相同数目的n个守卫, 我们按照第一排从左到右的顺序为国王和守卫分别编号为1到2*n+1。

在晚会上，兔子们的脸上都洋溢着幸福的笑容，兔子国王为了量化自己和守卫们的幸福度，就将晚会开始时，为第i个兔子分配一个幸福度记为a_i，当然这其中也包括国王自己的幸福度。

国王初始分配的幸福度总是在[0, m]之间。

在新年晚会结束之后，兔子国王和守卫们就会因为观看了精彩绝伦的晚会，幸福度都提升了x，即第i只兔子的幸福度变为了(a_i + x)

但是在晚会开始之前，国王和守卫们并不知道这场晚会的精彩程度如何，所以他们只能估计出x的范围在[L, R]之间。

现在国王希望计算，初始时他和守卫共有多少种不同的幸福度方案，能够使得晚会结束后，所有兔子的幸福度xor和可能为0。

输入格式

第一行四个整数n，m, L和R，意义如题目描述所示

输出格式

一行一个整数，表示可能的幸福度方案的数目，结果对1000000007取模

样例输入

1 3 1 3

样例输出

数据规模
对于20%的数据, 1 <= n, m <= 5, 1 <= L <= R <= 10
对于40%的数据, 1 <= n, m <= 100, 1 <= L <= R <= 100
对于70%的数据, 1 <= n, m <= 500, 1 <= L <= R <= 500
对于100%的数据, 1 <= n, m <= 1000, 1 <= L <= R <= 1000

样例解释
对于样例，共有以下几种分配幸福度的方案：
(0,1,2)
(0,2,1)
(0,2,3)
(0,3,2)
(1,0,2)
(1,2,0)
(2,0,1)
(2,0,3)
(2,1,0)
(2,3,0)
(3,0,2)
(3,2,0)

//贴份AC代码，表示看不懂

//大神路过请留言

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<iostream>

#include<algorithm>

#define FILE "xor"

typedef long long ll;

typedef double lf;

namespace IO{

    char buf[<<],*fs,*ft;

    inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;}

    inline int read(){

        int x=,rev=,ch=getc();

        while(ch<''||ch>''){if(ch=='-')rev=;ch=getc();}

        while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getc();}

        return rev?-x:x;

    }

}using namespace IO;

namespace Operation{

    const int dydxh(int(1e9)+);

    inline int add(int a,int b){return (a+=b)>=dydxh?a-dydxh:a;}

    inline int mul(int a,int b){return 1LL*a*b%dydxh;}

    inline int pow(int a,int b){int c=;for(;b;b>>=,a=mul(a,a))if(b&)c=mul(c,a);return c;}

    inline int inv(int a){return pow(a,dydxh-);}

}using namespace Operation;

const int MAXN(),D();

int n,m,L,R,ans,H,lim;

void init(){

    n=read()<<|,m=read(),L=read(),R=read();

    for(H=;H>=;H--)

        if(((m+R)>>H)&)

            break;

    lim=<<(++H);

}

int f[];

void FWT(int *f){

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

        for(int S=;S<lim;S++)

            if(!((S>>i)&)){

                int l=f[S],r=f[S|(<<i)];

                f[S]=add(l,r),f[S|(<<i)]=(l-r+dydxh)%dydxh;

            }

}

int count(int st){

    memset(f,,sizeof f);

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

        f[i]=;

    FWT(f);

    for(int S=;S<lim;S++)

        f[S]=pow(f[S],n);

    FWT(f);

    return mul(f[],inv(lim));

}

int main(){

    freopen(FILE".in","r",stdin);

    freopen(FILE".out","w",stdout);

    init();

    for(int k=L;k<=R;k++)

        ans=add(ans,count(k));

    printf("%d\n",ans);

    return ;

}

/*40分

#include<cstdio>

#include<cstring>

#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);

using namespace std;

const int N=1005;

const int mod=1e9+7;

int n,m,l,r,ans,f[N][N];

int main(){

    FRE(xor);

    scanf("%d%d%d%d",&n,&m,&l,&r);

    n=n<<1|1;

    for(int q=l;q<=r;q++){

        memset(f,0,sizeof f);

        f[0][0]=1;

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

            for(int j=0;j<=2*(m+q);j++){

                if(f[i][j]){

                    for(int k=q;k<=(m+q);k++){

                        f[i+1][j^k]+=f[i][j];

                        f[i+1][j^k]%=mod;

                    }

                }

            }

        }

        ans+=f[n][0];

        ans%=mod;

    }

    printf("%d\n",ans);

    return 0;

}

*/

巴特西

兔子的晚会 2016Vijos省选集训 day1

最新文章

热门文章