Submission #2239701


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;
typedef vector<unordered_map<lli,lli>> graph;

const lli mod = 1000000007;
lli n,a,b,c,d;
mat dp;

lli factorial(lli n){
  static lli dp[100000];
  if(dp[n]) return dp[n];
  if(n == 0) return dp[n] = 1;
  return dp[n] = (n*factorial(n-1))%mod;
}

lli pow(lli x,lli r,lli mod = 1000000007){
  lli ret = 1;
  for(;r != 0;r >>= 1){
    if(r&1 != 0) ret *= x,ret %= mod;
    x *= x,x %= mod;
  }
  return ret;
}

lli exeuclid(lli a,lli aa,lli x,lli xx,lli y,lli yy){
	lli q;
	if(a == 0) return aa > 0 ? xx : -xx;
	q = aa / a;
	return exeuclid(aa - q * a,a,xx - q * x,x,yy - q * y,y);
}


lli inverse(lli x){
	return (exeuclid(mod,x,0,1,1,0) + mod) % mod;
}


int main(){
  cin >> n >> a >> b >> c >> d;
  dp = mat(n+1,vll(n+1));
  dp[0][0] = 1;
  for(lli i = 1;i <= n;i++){
    for(lli j = 0;j <= n;j++){
      dp[i][j] = dp[i-1][j];
      if(i < a || i > b) continue;
      for(lli k = c;k <= d;k++){
        if(j-i*k < 0) break;
        lli x = dp[i-1][j-i*k];
        x = (x*factorial(j))%mod;
        x = (x*inverse(factorial(k)))%mod;
        x = (x*inverse(pow(factorial(i),k)))%mod;
        x = (x*inverse(factorial(j-i*k)))%mod;
        dp[i][j] += x;
      }
      dp[i][j] %= mod;
    }
  }
  cout << dp[n][n] << endl;
  return 0;

}

Submission Info

Submission Time
Task E - Grouping
User deoxy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1462 Byte
Status TLE
Exec Time 2104 ms
Memory 10112 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
TLE × 1
AC × 14
TLE × 1
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_many_01.txt, subtask_1_many_02.txt, subtask_1_many_03.txt, subtask_1_many_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_min_01.txt, subtask_1_randa_01.txt, subtask_1_randa_02.txt, subtask_1_randb_01.txt, subtask_1_randb_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt TLE 2104 ms 8064 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_many_01.txt AC 1953 ms 8064 KB
subtask_1_many_02.txt AC 1705 ms 10112 KB
subtask_1_many_03.txt AC 1958 ms 8064 KB
subtask_1_many_04.txt AC 1966 ms 8064 KB
subtask_1_max_01.txt AC 26 ms 8192 KB
subtask_1_max_02.txt AC 19 ms 8192 KB
subtask_1_min_01.txt AC 1 ms 256 KB
subtask_1_randa_01.txt AC 3 ms 2432 KB
subtask_1_randa_02.txt AC 1 ms 256 KB
subtask_1_randb_01.txt AC 7 ms 4992 KB
subtask_1_randb_02.txt AC 6 ms 384 KB