NC20222. [JSOI2016]位运算
描述
输入描述
第一行包含两个正整数N和K。
接下来一行包含一个由0和1组成的字符串S。
我们保证S的第一个字符一定为1。
输出描述
一行一个整数，表示选择的方案数对10^9+7取模的值。
示例1
输入:
3 1 100
输出:
1
说明:
对于第一个样例， 唯一的一种选择方法是选择 {1, 2, 3}。C++11(clang++ 3.9) 解法, 执行用时: 481ms, 内存消耗: 1128K, 提交时间: 2019-03-16 12:57:37
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 1000000007
using namespace std;
int n,k;
char s[1000];
struct mat{
int m[130][130];
mat(){
for (int i=0;i<(1<<n);i++)
for (int j=0;j<(1<<n);j++)
m[i][j]=0;
}
} a[2];
mat mul(mat a,mat b){
mat re;
for (int i=0;i<(1<<n);i++)
for (int j=0;j<(1<<n);j++)
for (int k=0;k<(1<<n);k++){
re.m[i][j]+=1ll*a.m[i][k]*b.m[k][j]%mo;
if (re.m[i][j]>=mo) re.m[i][j]-=mo;
}
return re;
}
int main(){
scanf("%d%d%s",&n,&k,&s);int len=strlen(s);
for (int zt=0;zt<(1<<n);zt++){
for (int zy=0;zy<(1<<n);zy++){
int td=0;
for (int i=1;i<=n;i++) if (zy&(1<<(i-1))) td++;
if (td&1) continue;
if (zt&1){
int ha=0;
for (int i=n;i;i--){
if (zy&(1<<(i-1))) ha=1;
if (zt&(1<<(i-1))) break;
}
if (ha) continue;
}
td=0;
for (int i=1;i<n;i++) if ((zy&(1<<(i-1)))&&!(zy&(1<<i))){
if (!(zt&(1<<i))) td=1;
}
if (td) continue;
int go=zt;
for (int i=1;i<n;i++) if (!(zy&(1<<(i-1)))&&(zy&(1<<i)))
go|=(1<<i);
a[0].m[go][zt]++;
}
}
for (int zt=0;zt<(1<<n);zt++){
for (int zy=0;zy<(1<<n);zy++){
int td=0;
for (int i=1;i<=n;i++) if (zy&(1<<(i-1))) td++;
if (td&1) continue;
int ha=0;
for (int i=n;i;i--){
if (zy&(1<<(i-1))) ha=1;
if (zt&(1<<(i-1))) break;
}
td=0;
for (int i=1;i<n;i++) if ((zy&(1<<(i-1)))&&!(zy&(1<<i))){
if (!(zt&(1<<i))) td=1;
}
if (td) continue;
int go=zt;
for (int i=1;i<n;i++) if (!(zy&(1<<(i-1)))&&(zy&(1<<i)))
go|=(1<<i);
if (!ha&&(go&1)) go^=1;
a[1].m[go][zt]++;
}
}
mat td,ret,lj,init;
for (int i=0;i<(1<<n);i++) td.m[i][i]=ret.m[i][i]=1;
for (int i=0;i<len;i++) td=mul(a[s[i]-'0'],td);
for (lj=td;k;k/=2,lj=mul(lj,lj)) if (k&1)
ret=mul(ret,lj);
init.m[1][0]=1;
ret=mul(ret,init);
printf("%d\n",ret.m[(1<<n)-2][0]);
}
C++14(g++5.4) 解法, 执行用时: 462ms, 内存消耗: 740K, 提交时间: 2020-06-09 14:23:42
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 7
#define S 50
#define X 1000000007
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int l,n,K,lim,op[1<<N],f[S+5][1<<N];char s[S+5];
struct M
{
int a[1<<N][1<<N];I M() {memset(a,0,sizeof(a));}
I int *operator [] (CI x) {return a[x];}
I M operator * (Con M& o) Con
{
RI i,j,k;M t;for(i=0;i^lim;++i) for(j=0;j^lim;++j)
for(k=0;k^lim;++k) t[i][j]=(1LL*a[i][k]*o.a[k][j]+t[i][j])%X;return t;
}
I M operator ^ (RI y) Con
{
M x=*this,t;for(RI i=0;i^lim;++i) t[i][i]=1;W(y) y&1&&(t=t*x,0),x=x*x,y>>=1;return t;
}
}U;
I int T(CI p,CI k,CI s)
{
RI i,x,y,t=0;for(i=n-1;i;--i) if(p>>i&1)
{if((x=(k>>i)&1)>(y=(k>>i-1)&1)) return -1;x==y&&(t|=1<<i);}
if(p&1) {if((x=k&1)>s) return -1;x==s&&(t|=1);}return t;
}
int main()
{
RI i,j,k,t;scanf("%d%d%s",&n,&K,s+1),l=strlen(s+1);
for(lim=1<<n,op[0]=i=1;i^lim;++i) op[i]=op[i>>1]^(i&1);
for(RI w=0;w^lim;++w)
{
memset(f,0,sizeof(f)),f[0][w]=1;
for(i=1;i<=l;++i) for(j=0;j^lim;++j) if(f[i-1][j])
for(k=0;k^lim;++k) op[k]&&~(t=T(j,k,s[i]&1))&&Inc(f[i][t],f[i-1][j]);
for(i=0;i^lim;++i) U[w][i]=f[l][i];
}return printf("%d",(U^K)[lim-1][0]),0;
}