题目描述
JYY 最近在研究位运算。他发现位运算中最有趣的就是异或 (xor) 运算。对于两个数的异或运算，JYY 发现了一个结论：两个数的异或值为
0
0
0 当且仅当他们相等。于是 JYY 又开始思考，对于
N
N
N 个数的异或值会有什么性质呢？
JYY 想知道，如果在
0
0
0 到
R
−
1
R-1
R−1 的范围内，选出
N
N
N 个不同的整数，并使得这
N
N
N 个整数的异或值为
0
0
0，那么一共有多少种选择的方法呢？（选择的不同次序并不作重复统计，请参见样例）
JYY 是一个计算机科学家，所以他脑海里的
R
R
R 非常非常大。为了能够方便的表达，如果我们将
R
R
R 写成一个
01
01
01 串，那么
R
R
R 是由一个较短的
01
01
01 串
S
S
S 重复
K
K
K 次得到的。比如，若
S
=
101
,
K
=
2
S=101,K=2
S=101,K=2，那么
R
R
R 的二进制表示则为
101101
101101
101101。由于计算的结果会非常大，JYY 只需要你告诉他选择的总数对
1
0
9
+
7
10^9+7
109+7 取模的结果即可。
数据范围
3
≤
N
≤
7
,
1
≤
k
≤
1
0
5
,
1
≤
∣
S
∣
≤
50
3\le N\le 7,1\le k\le 10^5,1\le |S|\le 50
3≤N≤7,1≤k≤105,1≤∣S∣≤50
题解
考虑到选出的数
x
i
x_i
xi 不同，
n
n
n 又很小，所以考虑状压，
f
i
,
s
f_{i,s}
fi,s 表示前
i
i
i 位，第
j
j
j 位状态表示
x
j
x_j
xj 小于或等于
x
j
+
1
x_{j+1}
xj+1 ，特殊的，我们设
x
n
+
1
=
R
x_{n+1}=R
xn+1=R 。
可以发现对于每个复读的串状态转移路径是相同的，于是矩乘即可。
代码
#include <bits/stdc++.h>
using namespace std
;
const int N
=130,P
=1e9+7;
int n
,k
,m
,a
[N
],al
,f
[N
][N
];
char ch
[N
];bool c
[N
];
struct Mat
{int p
[N
][N
];}F
,G
,V
;
int X(int x
){if (x
>=P
) x
-=P
;return x
;}
int work(int l
,int r
,int x
){
int v
=0;
for (int y
,z
,j
=1;j
<n
;j
++)
if (l
&(1<<j
)){
y
=(r
>>j
)&1;z
=(r
>>(j
-1))&1;
if (y
>z
) return -1;
if (y
==z
) v
|=(1<<j
);
}
if (l
&1){
if ((r
&1)>a
[x
]) return -1;
if ((r
&1)==a
[x
]) v
|=1;
}
return v
;
}
Mat
C(Mat A
,Mat B
){
for (int i
=0;i
<al
;i
++)
for (int j
=0;j
<al
;j
++){
V
.p
[i
][j
]=0;
for (int k
=0;k
<al
;k
++)
V
.p
[i
][j
]=X(V
.p
[i
][j
]+1ll*A
.p
[i
][k
]*B
.p
[k
][j
]%P
);
}
return V
;
}
int main(){
scanf("%d%d%s",&n
,&k
,ch
+1);m
=strlen(ch
+1);
for (int i
=1;i
<=m
;i
++) a
[i
]=ch
[i
]^48;al
=1<<n
;c
[0]=1;
for (int s
=1;s
<al
;s
++) c
[s
]=(!c
[s
-(s
&-s
)]);
for (int s
=0;s
<al
;s
++){
for (int i
=0;i
<=m
;i
++)
for (int j
=0;j
<al
;j
++)
f
[i
][j
]=0;
f
[0][s
]=1;
for (int i
=1,j
;i
<=m
;i
++)
for (int l
=0;l
<al
;l
++) if (f
[i
-1][l
])
for (int r
=0;r
<al
;r
++) if (c
[r
])
if (~(j
=work(l
,r
,i
)))
f
[i
][j
]=X(f
[i
][j
]+f
[i
-1][l
]);
for (int i
=0;i
<al
;i
++)
F
.p
[i
][s
]=f
[m
][i
];
}
for (int i
=0;i
<al
;i
++) G
.p
[i
][i
]=1;
for (;k
;k
>>=1,F
=C(F
,F
)) if (k
&1) G
=C(G
,F
);
printf("%d\n",G
.p
[0][al
-1]);
return 0;
}
