我居然还记得矩乘怎么写 真是感人
懵逼的 题目
BZOJ
扯淡的 题解
{x xor 3x = 2x} => {x xor 2x = 3x} => {x xor 2x = x + 2x} => {x没有相邻的1}
没有相邻的\(1\),
第一问用数位DP就完事了
第二问我没有想到会有两个\(1\)中间隔着不只一个\(0\)的情况然后写了个\(2^\frac{n}{2} \cdot 2^{n - \frac{n}{2}} -
1\)就GG了
我们发现第二问这个玩意是可以递推的, 设答案为\(S_n\), 如果在\(S_{n - 1}\)后面加\(0\)(指二进制下), 或者在\(S_{n - 2}\)后面加\(01\)就包含了所有的情况, 所以\(S_n = S_{n - 1} + S_{n - 2} \to \{S_n\} =
\{fib_n\}\), 矩乘一下就完事了
沙茶的 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
#define MOD (1000000000 + 7)
#define MAXL (60 + 5)
using namespace std;
struct matrix {
LL n, m, zh[3][3];
}sou, m1;
LL n, a[MAXL], f[MAXL][2][2];
void solve() {
memset(f, 0, sizeof(f));
f[0][1][0] = 1;
for (int i = 0; i < a[0]; i++)
for (int up = 0; up <= 1; up++)
for (int ln = 0; ln <= 1; ln++)
for (int nn = 0; nn <= 1; nn++) {
if (up && nn > a[i + 1]) continue;
if (ln && nn) continue;
int nup = (up & (a[i + 1] == nn));
f[i + 1][nup][nn] += f[i][up][ln];
}
LL ans = 0;
for (int up = 0; up <= 1; up++)
for (int ln = 0; ln <= 1; ln++)
ans += f[a[0]][up][ln];
printf("%lld\n", ans - 1);
}
matrix mult(matrix a, matrix b) {
matrix re;
re.n = a.n, re.m = b.m;
memset(re.zh, 0, sizeof(re.zh));
for (int i = 1; i <= a.n; i++)
for (int j = 1; j <= b.m; j++)
for (int k = 1; k <= b.n; k++)
re.zh[i][j] = (re.zh[i][j] + (a.zh[i][k] * b.zh[k][j]) % MOD) % MOD;
return re;
}
matrix ksm(LL b) {
if (b == 1) return m1;
matrix re = ksm(b >> 1);
re = mult(re, re);
if (b & 1) re = mult(re, m1);
return re;
}
int main() {
sou.n = 1, sou.m = 2, sou.zh[1][1] = sou.zh[1][2] = 1;
m1.n = m1.m = 2, m1.zh[1][2] = m1.zh[2][1] = m1.zh[2][2] = 1;
int t;
scanf("%d", &t);
while (t--) {
scanf("%lld", &n);
a[0] = 0;
while (n >= (1ll << a[0])) ++a[0];
for (int i = 1; i <= a[0]; i++) a[i] = ((n & (1ll << (a[0] - i))) > 0);
solve();
printf("%lld\n", mult(sou, ksm(n)).zh[1][2]);
}
return 0;
}
|
By 准备退役旅游的Cansult