题意：给定一个数N，表示有N个位置，要么放置0，要么放置1，问至少存在一个连续的M个1的放置方式有多少？
分析：正面求解可能还要考虑到重复计算带来的影响，该题适应反面求解。设dp[i][j]表示到前 i 为后导 1 个数为 j 的方案数，于是有动态规划方程：
dp[i][0] = sum{ dp[i-1][0... min(i-1, M) ] };
dp[i][j] = dp[i-1][j-1] 其中 j != 1
单单根据这个方程时间度为O(N*M)，还是不足以在有限的时间内解出该问题。通过观察我们发现方程可以简化，即后一层的和值是上一层和值的两倍减去上层的最后一个值。于是可以维护一个最后一个值得队列，然后计算出首行的和值即可。注意首行是表示状态数达到M个的行。
代码如下：
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; typedef long long LL;
const int mod = int(1e9)+;
int N, M;
queue<int>q;
int pp[]; LL _pow(LL a, int b) {
LL ret = ;
while (b) {
if (b & ) ret = (ret * a) % mod;
b >>= ;
a = (a * a) % mod;
}
return ret;
} void gao() {
int ret = ;
while (!q.empty()) q.pop();
pp[] = , pp[] = ;
q.push(pp[]);
q.push(pp[]);
for (int i = ; i < M; ++i) {
pp[i] = (1LL * pp[i-] * ) % mod;
ret = (1LL * ret + pp[i]) % mod;
q.push(pp[i]);
}
for (int i = M; i <= N; ++i) {
q.push(ret);
ret = (1LL * ret * - q.front() + mod) % mod;
q.pop();
}
printf("%d\n", (1LL * _pow(, N) - ret + mod) % mod);
} int main() {
while (scanf("%d %d", &N, &M) != EOF) {
if (N == || M > N) {
puts("");
continue;
}
if (M == ) {
printf("%d\n", _pow(, N));
continue;
}
if (M == ) {
printf("%d\n", (_pow(, N)-+mod)%mod);
continue;
}
gao();
}
return ;
}