---

title: 【luogu-1077】摆花 date: 2019-10-28 21:06:48 tags:

方程

设计状态$f[j][i]$摆了前$j$盆花，用到了第$i$种，总共方案数。

每盆花在摆的过程中只有在换花的时候会产生不同的方案，也就是是否继续摆这个花或者换花摆，这是一个决策。

所以在转移的过程中，需要从这个点入手

当我摆到第$j$盆花的时候，我会思考当前这个花要摆的个数，叠加多种情况。

$$f[j][i] = \sum_{k = 0}^{cnt[i]} f[j - k][i - 1]$$

$f[j][i]$摆了前$j$盆花，用到了第$i$种，总共方案数。$cnt[i]$是第$i$种花的数量，$\sum_{k = 0}^{cnt[i]}$就是累加，第$i$种花选不同个数的方案数。

/*!
 * FileName: luogu-1077.cpp
 * This Problem is on luogu. The ID of the problem is 1077. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-10-25 20:25:52 written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 0x7fffffff
#define _R register
using namespace std;
const int _ = 1e2 + 10;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int f[_][_];
int A[_];
int n;
int m;
const int MOD = 1000007;
int main()
{
    n = read(); m = read();
    for(_R int i = 1;i <= n;i++) A[i] = read();
    for(_R int i = 0;i <= n;i++)  f[0][i] = 1;
    for(_R int i = 1;i <= n;i++) {
        for(_R int j = 1;j <= m;j++) {
            for(_R int k = 0;k <= A[i];k++)
                if(j - k >= 0)
                    f[j][i] += f[j - k][i - 1];
                else break;
            f[j][i] %= MOD;
        }
    }
    printf("%d", f[m][n] % MOD);
    return 0;
}