Submission #499848

#TimeUsernameProblemLanguageResultExecution timeMemory
499848keta_tsimakuridzeNoM (RMI21_nom)C++14
52 / 100
35 ms10112 KiB
#include<bits/stdc++.h> #define int long long #define f first #define s second #define pii pair<int,int> using namespace std; const int N = 2000 + 5, mod = 1e9 + 7; // ! int t, dp[N][N], fact[N], invfact[N],x[N],d[N]; int pwr(int u,int v) { int ans = 1; while(v) { if(v % 2) ans = ans * u % mod; v /= 2; u = u * u % mod; } return ans; } int A(int a,int b) { if(a < 0) return 0; if(a < b) return 0; return fact[a] * invfact[a - b] % mod; } int c(int a,int b) { if(a < b || a < 0) return 0; return fact[a] * invfact[a - b] % mod * invfact[b] % mod; } main(){ int n , m; cin >> n >> m; for(int i = 1; i <= 2 * n; i++) { x[i % m + 1]++; } fact[0] = invfact[0] = 1; for(int i = 1; i <= 2 * n; i++) fact[i] = fact[i - 1] * i % mod, invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod; int cur = 0; dp[0][0] = 1; for(int i = 1; i <= m; i++) { for(int j = 0; j <= cur; j++) { for(int k = 0; k <= x[i]; k += 2) { dp[i][j + k / 2] += dp[i - 1][j] * A(x[i], k) % mod * c(n - j, k / 2) % mod; dp[i][j + k / 2] %= mod; } } // cout << dp[i][2] <<" "<< c[i] << endl; cur += x[i]; // for(int j = 0; j <= cur; j++) cout<<dp[i][j] <<" "; cout << endl; } for(int i = n; i >= 0; i--) { d[i] = dp[m][i] * fact[2 * n - i * 2] % mod; for(int j = i + 1; j <= n; j++) { d[i] -= d[j] * c(j, i) % mod; d[i] += mod; d[i] %= mod; } } cout << d[0]; }

Compilation message (stderr)

Main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...