动态规划。 首先，i+1长度包含j个1子串的个数至少等于i长度包含j个1的子串的个数2（在数字串的后面添加0或1），再加上i+1长度数字串中结尾是j个1的子串个数，最后除去重复计算的i+1长度数字串前i-(j-1)个数字有j个1的子串个数。
#include <iostream> #include <cmath> using namespace std; int main() { int m, n; long long num[32][32]; for(int i=1;i<32;++i){num[i][i]=1;} for(int i=2;i<32;++i) for(int j=1;j<i;++j){ num[i][j]=2*num[i-1][j]+int(pow(2.0,double(i-j-1))); if(i>2*j) num[i][j]-=num[i-j-1][j];} cin>>m>>n; while(m+1&&n+1){ cout<<num[m][n]<<endl; cin>>m>>n;} return 0; }
一开始看这题，像排列组合的问题。不过用动态规划思想直接做就行。
设 $dp(m, n)$：长度为 $n$ 的 BitString，其中「包含至少 $m$ 个连续 1」的子串的个数。
如果前 $n-1$ 个位已经有 $m$ 个连续 1 的子串，那么 $dp(m, n)$ 当然包含它们；而且由于新的一位可以是 0 也可以是 1，所以应该是 $2\times dp(m, n - 1)$。
如果前 $n-1$ 位里没有 $m$ 个连续 1 的子串，那么只有一种情况下加上一个 1 可以引入 连续 $m$ 个 1，那就是前面 $n-1$ 个位中，最后 $m-1$ 个都是 1 且倒数第 $m$ 个是 0（不然就有 $m$ 个连续 1 了）。这样，还剩下 $n-m-1$ 位没有确定。这一部分也不能有 $m$ 个连续的 1。很显然，总共有 $2^{n - m - 1}$ 种长为 $n-m-1$ 的串，其中有 $dp(m, n - m - 1)$ 个串是含有 $m$ 个连续 1 子串的。所以相反的有 $2^{n - m - 1} - dp(m, n - m - 1)$ 个串没有 $m$ 个连续的 1。
然后再考虑特殊情况即可。综上，可以得到以下式子。 $$ dp(m, n) = \begin{cases}0&n < m\ 1&n=m\ 2\times dp(m, n - 1) + 2^{n - m - 1} - dp(m, n - m - 1)&n>m\end{cases} $$ 楼上的大佬把我这里三种情况中的一些合并了一下，写成了 if 分支。我把它们分开写了。
if
代码
#include "bits/stdc++.h" using namespace std; using i64 = int64_t; using u64 = uint64_t; int main() { u64 dp[32][32]; // array<array<u64, 32>, 32> dp; for (u64 i = 0; i < 32; ++i) { for (u64 j = 0; j < i; ++j) { dp[i][j] = 0; } dp[i][i] = 1; for (u64 j = i + 1; j < 32; ++j) { dp[i][j] = 2 * dp[i][j - 1] + (1 << (j - i - 1)) - dp[i][j - i - 1]; } } for (i64 n, m; cin >> n >> m, n != -1;) { cout << dp[m][n] << '\n'; } }
OJ 的数学公式不能换行，所以只能那样了似乎。
动态规划。
首先，i+1长度包含j个1子串的个数至少等于i长度包含j个1的子串的个数2（在数字串的后面添加0或1），再加上i+1长度数字串中结尾是j个1的子串个数，最后除去重复计算的i+1长度数字串前i-(j-1)个数字有j个1的子串个数。
[EOJ 2854] 统计特定字串模式的个数
设 $dp(m, n)$：长度为 $n$ 的 BitString，其中「包含至少 $m$ 个连续 1」的子串的个数。
如果前 $n-1$ 个位已经有 $m$ 个连续 1 的子串，那么 $dp(m, n)$ 当然包含它们；而且由于新的一位可以是 0 也可以是 1，所以应该是 $2\times dp(m, n - 1)$。
如果前 $n-1$ 位里没有 $m$ 个连续 1 的子串，那么只有一种情况下加上一个 1 可以引入 连续 $m$ 个 1，那就是前面 $n-1$ 个位中，最后 $m-1$ 个都是 1 且倒数第 $m$ 个是 0（不然就有 $m$ 个连续 1 了）。这样，还剩下 $n-m-1$ 位没有确定。这一部分也不能有 $m$ 个连续的 1。很显然，总共有 $2^{n - m - 1}$ 种长为 $n-m-1$ 的串，其中有 $dp(m, n - m - 1)$ 个串是含有 $m$ 个连续 1 子串的。所以相反的有 $2^{n - m - 1} - dp(m, n - m - 1)$ 个串没有 $m$ 个连续的 1。
然后再考虑特殊情况即可。综上，可以得到以下式子。
$$
dp(m, n) = \begin{cases}0&n < m\ 1&n=m\ 2\times dp(m, n - 1) + 2^{n - m - 1} - dp(m, n - m - 1)&n>m\end{cases}
$$
楼上的大佬把我这里三种情况中的一些合并了一下，写成了
if分支。我把它们分开写了。代码
OJ 的数学公式不能换行，所以只能那样了似乎。