lightoj 1145

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1145

题解：首先只要是dp的值只和上一个状态有关系那么就可以优化一维，然后这题不妨设dp[2][M],表示和为1～M的一共有多少种有种前缀的思想。

然后dp[][M]=dp[][M-1]-dp[M-k]。

#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 100000007
using namespace std;
typedef long long ll;
const int M = 1e5 + 10;
ll dp[2][M];
int main() {
    int t , Case = 0;
    scanf("%d" , &t);
    while(t--) {
        int n , k , s;
        scanf("%d%d%d" , &n , &k , &s);
        memset(dp , 0 , sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1 ; i <= n ; i++) {
            ll sum = 0;
            for(int j = 0 ; j <= s ; j++) {
                dp[i % 2][j] = sum;
                if(j < k) sum = (sum % mod + dp[(i - 1) % 2][j] % mod + mod) % mod;
                else sum = (sum % mod + dp[(i - 1) % 2][j] % mod - dp[(i - 1) % 2][j - k] % mod + mod) % mod;
            }
        }
        printf("Case %d: %lld
" , ++Case , dp[n % 2][s] % mod);
    }
    return 0;
}