fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long mod = 1e9 + 7;
  4. long long fact[1005];
  5. long long dp[1003][1003];
  6. long long bigmod(long long a, long long p){
  7.     if(p == 0){
  8.         return 1;
  9.     }
  10.     long long ans = bigmod(a, p/2);
  11.     ans = (ans * ans) % mod;
  12.     if(p % 2 == 1){
  13.         ans = (ans * a) % mod;
  14.     }
  15.     return ans;
  16. }
  17. long long inverse(long long a){
  18.     return bigmod(a, mod - 2);
  19. }
  20. long long nCr(long long n, long long r){
  21.     return (fact[n] * inverse((fact[r] * fact[n - r]) % mod)) % mod;
  22. }
  23. long long group(long long a, long long k){
  24.     long long x = fact[a * k];
  25.     long long y = (bigmod(fact[a], k) * fact[k]) % mod;
  26.     return (x * inverse(y)) % mod;
  27. }
  28. int main(){
  29.     fact[0] = 1;
  30.     for(long long i = 1; i <= 1002; i++){
  31.         fact[i] = (fact[i - 1] * i) % mod;
  32.     }
  33.     int n, a, b, c, d;
  34.     cin >> n >> a >> b >> c >> d;
  35.     for(int i = 0; i <= b; i++){
  36.         for(int j = 0; j <= n; j++){
  37.             dp[i][j] = 0;
  38.         }
  39.         dp[i][0] = 1;
  40.     }
  41.     for(long long i = a; i <= b; i++){
  42.         for(long long j = 1; j <= n; j++){
  43.             dp[i][j] = dp[i - 1][j];
  44.             for(long long k = c; k <= d; k++){
  45.                 if(j - k * i < 0){
  46.                     break;
  47.                 }
  48.                 long long cur = (nCr(j, k * i) * dp[i - 1][j - k * i]) % mod;
  49.                 cur = (cur * group(i, k)) % mod;
  50.                 dp[i][j] = (dp[i][j] + cur) % mod;
  51.             }
  52.         }
  53.     }
  54.     cout << dp[b][n];
  55.     return 0;
  56. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
7 2 3 1 3
stdout
copy 
105
https://ideone.com/2BVewv
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!