题意

在0和1组成的长度为$n(1 \le n \le 31)$的字符串中，统计包含$m(1 \le m \le n)$个连续1子串的字符串的个数。

题解

这题要用到的算法思想是动态规划。

首先令$f(n, m)$表示长度为$n(1 \le n \le 31)$的字符串中，包含$m(1 \le m \le n)$个连续1子串的字符串的个数。考虑最后一位，也就是第$n$位的取值，可以分为两种情况：

如果第$n$位为0，那么只能在前面的$n-1$位里取长度为$m$的连续1子串，那么答案就是
\[f(n-1,m)\]
如果第$n$位为1，那么考虑两种情况。
一种是最后$m$位全为1，那么前面$n-m$位就可以任意取值，答案为
\[2^{n-m}\]
另一种情况是最后$m$位不全为1，也就是存在某一位为0，枚举最后一位0出现的位置，可能出现在第$n-1$位、第$n-2$位，一直到第$n-m+1$位，不管最后一个0出现在哪里，都要在之前的字符串中重新出现长度为$m$的连续1子串，所以答案是
\[\sum\limits_{n - m \le i \le n - 2} {f(i,m)} \]

所以最终的答案就是
\[f(n,m) = {2^{n - m}} + \sum\limits_{n - m \le i \le n - 1} {f(i,m)} \]
进一步化简这个式子，用$n-1$替换$n$可以得到
\[f(n - 1,m) = {2^{n - m - 1}} + \sum\limits_{n - m - 1 \le i \le n - 2} {f(i,m)} \]
两式相减可以得到
\[f(n,m) = {2^{n - m - 1}} + 2f(n - 1,m) - f(n - m - 1,m)\]
边界条件为：

当$n < m$时，$f(n,m)=0$。
当$n = m$时，$f(n,m)=1$。

代码

#include <bits/stdc++.h>
using namespace std;

int f(int n, int m) {
	if (n < m) return 0;
	if (n == m) return 1;
	int res = 2 * f(n - 1, m) - f(n - m - 1, m) + (1 << (n - m - 1));
	return res;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) && (n != -1 || m != -1)) {
    	int res = f(n, m);
    	printf("%d\n", res);
    }
    return 0;
}