0左边必有1的二进制字符串的数量
题目描述
给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。
输入描述：
输入一行，包含一个整数
n
(
1
≤
n
≤
2
∗
1
0
7
)
n(1 \leq n \leq2*10^7)
n(1≤n≤2∗107)。
输出描述：
输出一个整数，表示返回的答案，由于字符串的数量巨大，可能会溢出，请输出对
2
29
2^{29}
229取模后的答案。
示例1
输入
1
输出
1
说明
只有“1”满足
示例2
输入
2
输出
2
说明
只有“10”和“11”满足
示例3
输入
3
输出
3
说明
只有“101”，“110”，“111”满足
题解：
我们在纸上画画可以发现前几项为：1 2 3 5 8 13 …，明显的斐波那契数列。数据范围有点大，
O
(
n
)
O(n)
O(n) 应该过不了，使用矩阵快速幂就完事了。
代码：
#include <cstdio>
#include <cstring>
using namespace std
;
const long MOD
= 1 << 29;
int n
;
long c
[2][2];
void matmul(long a
[][2], long b
[][2]) {
memset(c
, 0, sizeof c
);
for (int i
= 0; i
< 2; ++i
) {
for (int j
= 0; j
< 2; ++j
) {
for (int k
= 0; k
< 2; ++k
) {
c
[i
][j
] += a
[i
][k
] * b
[k
][j
] % MOD
;
c
[i
][j
] %= MOD
;
}
}
}
memcpy(a
, c
, sizeof c
);
}
int solve(int m
) {
long ans
[][2] = { {1,1}, {1,0} };
long ret
[][2] = { {1,0}, {0,1} };
while (m
) {
if (m
& 1) matmul(ret
, ans
);
matmul(ans
, ans
);
m
>>= 1;
}
return ret
[0][0];
}
int main(void) {
scanf("%d", &n
);
if (n
< 3) return 0 * printf("%d\n", n
);
printf("%d\n", solve(n
));
return 0;
}
