https://ac.nowcoder.com/acm/contest/317/F

C++版本一

std

题解：DP

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5001, mod = 1e9 + 7;
int N, V, a[MAXN],  f[MAXN][MAXN], Lim, x[MAXN], y[MAXN], g[MAXN][MAXN];
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
void add2(int &x, int y) {
    if(x + y < 0) x = (x + y + mod);
    else x = (x + y >= mod ? x + y - mod : x + y);
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int main() {
    //freopen("a.in", "r", stdin);
    cin >> N >> V; Lim = V;
    for(int i = 1; i <= Lim; i++) g[1][i] = add(i, g[1][i - 1]), f[1][i] = 1;
    for(int x = 2; x <= N; x++) {
        for(int y = 0; y <= Lim; y++) {
            f[x][y] = 1;
            add2(f[x][y], g[x - 1][y - 1]);
            g[x][y] = add(add(add(g[x][y - 1], mul(f[x][y], y)), g[x - 1][y]), -g[x - 1][y - 1]);
        }
    }
//    cout << g[N][Lim] << endl; 
    for(int x = 1; x <= N; x++) 
        for(int y = 2; y <= Lim; y++) 
            add2(f[x][y], f[x][y - 1]);
    int ans = 0;
    for(int i = 1; i <= N; i++) add2(ans, f[i][V]);
    cout << ans;
    return 0;
}