4851: [Jsoi2016]位运算
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 12 Solved: 7
[Submit][Status][Discuss]
Description
JYY最近在研究位运算。他发现位运算中最有趣的就是异或（xor）运算。对于两个数的异或运算，JYY发现了一个
结论：两个数的异或值为0当且仅当他们相等。于是JYY又开始思考，对于N个数的异或值会有什么性质呢？
【问题描述】
JYY想知道，如果在0到R-1的范围内，选出N个不同的整数，并使得这N个整数的异或值为0，那么一共有多少种选择
的方法呢？（选择的不同次序并不作重复统计，请参见样例）JYY是一个计算机科学家，所以他脑海里的R非常非常
大。为了能够方便的表达，如果我们将R写成一个0-1串，那么R是由一个较短的0-1串S重复K次得到的。比如，若S=
“101”，K=2，那么R的2进制表示则为“101101”。由于计算的结果会非常大，JYY只需要你告诉他选择的总数对1
0^9+7取模的结果即可
Input
第一行包含两个正整数N和K。
接下来一行包含一个由0和1组成的字符串S。
我们保证S的第一个字符一定为1。
3<=N<=7,1<=k<=10^5,1<=|S|<=50
Output
一行一个整数，表示选择的方案数对10^9+7取模的值。
Sample Input
3 1
100
100
Sample Output
1
对于第一个样例， 唯一的一种选择方法是选择 {1, 2, 3}。
对于第一个样例， 唯一的一种选择方法是选择 {1, 2, 3}。
HINT
Source
从高到低确定n个数的每一位 填的过程中保持n个数从小到大 每一位1的个数都要是偶数
填完前i位后 n个数可能有相等 形成若干段区间 记一下区间间隔的位置
因为要求小于R 再记一下最大的数是否等于s的前i位
然后分i+1位是0/1转移一下
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mo 1000000007 5 using namespace std; 6 int n,k; 7 char s[1000]; 8 struct mat{ 9 ????int m[130][130];10 ????mat(){11 ????????for (int i=0;i<(1<<n);i++)12 ????????????for (int j=0;j<(1<<n);j++)13 ????????????????m[i][j]=0;14 ????}15 } a[2];16 mat mul(mat a,mat b){17 ????mat re;18 ????for (int i=0;i<(1<<n);i++)19 ????????for (int j=0;j<(1<<n);j++)20 ????????????for (int k=0;k<(1<<n);k++){21 ????????????????re.m[i][j]+=1ll*a.m[i][k]*b.m[k][j]%mo;22 ????????????????if (re.m[i][j]>=mo) re.m[i][j]-=mo;23 ????????????}24 ????return re;25 }26 int main(){27 ????scanf("%d%d%s",&n,&k,&s);int len=strlen(s);28 ????29 ????for (int zt=0;zt<(1<<n);zt++){30 ????????for (int zy=0;zy<(1<<n);zy++){31 ????????????int td=0;32 ????????????for (int i=1;i<=n;i++) if (zy&(1<<(i-1))) td++;33 ????????????if (td&1) continue;34 35 ????????????if (zt&1){36 ????????????????int ha=0;37 ????????????????for (int i=n;i;i--){38 ????????????????????if (zy&(1<<(i-1))) ha=1;39 ????????????????????if (zt&(1<<(i-1))) break;40 ????????????????}41 ????????????????if (ha) continue;42 ????????????}43 ????????????44 ????????????td=0;45 ????????????for (int i=1;i<n;i++) if ((zy&(1<<(i-1)))&&!(zy&(1<<i))){46 ????????????????if (!(zt&(1<<i))) td=1;47 ????????????}48 ????????????if (td) continue;49 ????50 ????????????int go=zt;51 ????????????for (int i=1;i<n;i++) if (!(zy&(1<<(i-1)))&&(zy&(1<<i)))52 ????????????????go|=(1<<i);53 ????????????a[0].m[go][zt]++;54 ????????}55 ????}56 57 ????for (int zt=0;zt<(1<<n);zt++){58 ????????for (int zy=0;zy<(1<<n);zy++){59 ????????????int td=0;60 ????????????for (int i=1;i<=n;i++) if (zy&(1<<(i-1))) td++;61 ????????????if (td&1) continue;62 63 ????????????int ha=0;64 ????????????for (int i=n;i;i--){65 ????????????????if (zy&(1<<(i-1))) ha=1;66 ????????????????if (zt&(1<<(i-1))) break;67 ????????????}68 ????????????69 ????????????td=0;70 ????????????for (int i=1;i<n;i++) if ((zy&(1<<(i-1)))&&!(zy&(1<<i))){71 ????????????????if (!(zt&(1<<i))) td=1;72 ????????????}73 ????????????if (td) continue;74 ????75 ????????????int go=zt;76 ????????????for (int i=1;i<n;i++) if (!(zy&(1<<(i-1)))&&(zy&(1<<i)))77 ????????????????go|=(1<<i);78 ????????????if (!ha&&(go&1)) go^=1;79 ????????????a[1].m[go][zt]++;80 ????????}81 ????}82 ????83 ????mat td,ret,lj,init;84 ????for (int i=0;i<(1<<n);i++) td.m[i][i]=ret.m[i][i]=1;85 ????for (int i=0;i<len;i++) td=mul(a[s[i]-‘0‘],td);86 ????for (lj=td;k;k/=2,lj=mul(lj,lj)) if (k&1)87 ????????ret=mul(ret,lj);88 ????init.m[1][0]=1;89 ????ret=mul(ret,init);90 ????printf("%d\n",ret.m[(1<<n)-2][0]);91 }bzoj4851: [Jsoi2016]位运算
原文地址：http://www.cnblogs.com/lengtouqing/p/7616988.html