Submission #47834810

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std; 
const int P = 1000000007; 

int poww(int a, int b) {
    int r = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P; 
    return r; 
}

int n, a, b, c, d; 
int f[1005][1005]; // 人数为 i 的组，用了 j 人
int g[1005][1005]; 
int fac[1005], ifac[1005]; 
inline int C(int n, int m) {
    if (n < m) return 0; 
    return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; 
}

int main(void) {
    cin >> n >> a >> b >> c >> d; 
    for (int i = fac[0] = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % P; 
    ifac[n] = poww(fac[n], P - 2); 
    for (int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P; 

    for (int i = 1; i <= n; ++i) {
        g[i][0] = 1; 
        for (int k = 1; k <= n; ++k)
            g[i][k] = 1ll * g[i][k - 1] * C(k * i, i) % P; 
    }

    f[a - 1][0] = 1; 
    for (int i = a; i <= b; ++i)
        for (int j = 0; j <= n; ++j) {
            f[i][j] = f[i - 1][j]; 
            for (int k = c; k <= d && k * i <= j; ++k) {
                int v = 1ll * g[i][k] * ifac[k] % P; 
                // printf("%d %d %d %d %d\n", i, k, g[i][k], ifac[k], v); 
                f[i][j] = (f[i][j] + 1ll * f[i - 1][j - k * i] * C(n - j + k * i, k * i) % P * v) % P; 
            }
        }
    cout << f[b][n] << "\n"; 
    return 0; 
}

Submission Info

Judge Result