再次被初中的自己搏杀，想到网络流去了

Link

T404546 亮亮的玫瑰问题 2

Question

有 \(n\) 种花，第 \(i\) 种花有 \(a_i\) 个，求需要摆 \(m\) 朵花的方案数

Solution

定义 \(F[i][j]\) 表示前 \(i\) 种花，已经摆了 \(j\) 个的方案数

枚举第 \(i\) 种花需要摆多少个 \(k\)

所以 \(F[i][j]=\sum\limits_{k=0}^{min(j,a[i])} F[i-1][j-k]\)

答案就是 \(F[n][m]\)

Code

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL TT=1e6+7;
const int maxn=1e2+4;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;

int n,m;
int a[maxn];
LL F[maxn][maxn];
int main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++) fin>>a[i];
    F[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=min(j,a[i]);k++)
                F[i][j]=(F[i][j]+F[i-1][j-k])%TT;
    fout<<F[n][m]<<'\n';
    return 0;
}