题意:一个兔子要吃红萝卜和白萝卜(排成一排),但是吃白萝卜时必须吃连续的 k 个,t 个询问(1 ≤ t, k ≤ 10^5),每个询问为a, b (1 ≤ ai ≤ bi ≤ 10^5),问长度为 a 到长度为 b 的区间有几种符合这只兔子吃法的排列有多少种。。
题目链接:http://codeforces.com/problemset/problem/474/D
——>>状态:dp[i] 表示前 i 个萝卜符合要求的排列总数
状态转移方程:dp[i] = (dp[i - 1] + dp[i - k]) % MOD;
加上预处理OK。。
(输入开挂46MS,比不开挂的 78MS 短。。)
#include <cstdio> const int MOD = 1000000007; const int MAXN = 100000; int t, k; int dp[MAXN + 10], sum[MAXN + 10]; void Init() { dp[0] = 1; sum[0] = 0; for (int i = 1; i <= MAXN; ++i) { dp[i] = dp[i - 1]; if (i >= k) { dp[i] = (dp[i] + dp[i - k]) % MOD; } sum[i] = (sum[i - 1] + dp[i]) % MOD; } } int ReadInt() { int ret = 0; char ch; while ((ch = getchar()) && ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; } return ret; } void Solve() { int a, b; getchar(); while (t--) { // scanf("%d%d", &a, &b); a = ReadInt(); b = ReadInt(); printf("%d\n", ((sum[b] - sum[a - 1]) % MOD + MOD) % MOD); } } int main() { while (scanf("%d%d", &t, &k) == 2) { Init(); Solve(); } return 0; }