首页 > 代码库 > 兔子的晚会 2016Vijos省选集训 day1
兔子的晚会 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
样例输出
12
数据规模
对于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[1<<15],*fs,*ft; inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ int x=0,rev=0,ch=getc(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)rev=1;ch=getc();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getc();} return rev?-x:x; }}using namespace IO;namespace Operation{ const int dydxh(int(1e9)+7); 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=1;for(;b;b>>=1,a=mul(a,a))if(b&1)c=mul(c,a);return c;} inline int inv(int a){return pow(a,dydxh-2);}}using namespace Operation;const int MAXN(2000),D(48);int n,m,L,R,ans,H,lim;void init(){ n=read()<<1|1,m=read(),L=read(),R=read(); for(H=31;H>=0;H--) if(((m+R)>>H)&1) break; lim=1<<(++H);}int f[2048];void FWT(int *f){ for(int i=0;i<H;i++) for(int S=0;S<lim;S++) if(!((S>>i)&1)){ int l=f[S],r=f[S|(1<<i)]; f[S]=add(l,r),f[S|(1<<i)]=(l-r+dydxh)%dydxh; }}int count(int st){ memset(f,0,sizeof f); for(int i=st;i<=st+m;i++) f[i]=1; FWT(f); for(int S=0;S<lim;S++) f[S]=pow(f[S],n); FWT(f); return mul(f[0],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 0;}/*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