Submission #857755

#TimeUsernameProblemLanguageResultExecution timeMemory
857755divadNoM (RMI21_nom)C++14
9 / 100
9 ms63356 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int MOD = 1e9+7; const int NMAX = 2e3+2; int n,m,cnt[NMAX]; /// dp[i][j] = cate imperecheri pot obtine cu primele i resturi si sa ramana j neimperecheata struct Mint{ int val; Mint(){ val = 0; } Mint(int _val){ val = _val%MOD; } Mint operator * (Mint oth) { return (val * oth.val); } Mint operator * (int oth) { return (val * oth); } Mint operator + (Mint oth) { return (val + oth.val); } Mint operator - (Mint oth) { return (val - oth.val + MOD); } Mint operator = (int oth){ val = oth; return *this; } Mint operator += (Mint oth){ val += oth.val; return *this; } } fact[2*NMAX], inv[2*NMAX], dp[NMAX][2*NMAX]; Mint lgput(int n, int a){ if(a == 0){ return 1; }else{ if(a%2 == 0){ Mint val = lgput(n, a/2); return val*val; }else{ return lgput(n, a-1)*n; } } } Mint comb(int n, int m){ return fact[n]*inv[n-m]*inv[m]; } Mint aranj(int n, int m){ return fact[n]*inv[n-m]; } signed main() { fact[0] = 1; for(int i = 1; i < NMAX*2; i++){ fact[i] = fact[i-1]*i; } inv[NMAX*2-1] = lgput(fact[NMAX*2-1].val, MOD-2); for(int i = NMAX*2-2; i >= 0; i--){ inv[i] = inv[i+1]*(i+1); } cin >> n >> m; for(int i = 1; i <= 2*n; i++){ cnt[i%m]++; } dp[0][cnt[0]] = 1; int maxi = cnt[0]; for(int i = 1; i < m; i++){ for(int k = 0; k <= cnt[i]; k++){ for(int j = k; j <= maxi; j++){ /// (i-1, j) -> (i, j-k+(cnt[i]-k)) dp[i][j-k+(cnt[i]-k)] += dp[i-1][j]*aranj(cnt[i], k)*comb(j, k); } } maxi += cnt[i]; } dp[m-1][0] = dp[m-1][0]*fact[n]; dp[m-1][0] = dp[m-1][0]*lgput(2, n); cout << dp[m-1][0].val; return 0; }
#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...