Submission #540138

#TimeUsernameProblemLanguageResultExecution timeMemory
540138dooweyNoM (RMI21_nom)C++14
9 / 100
1 ms984 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 2010; const int M = N * 2; const int MOD = (int)1e9 + 7; int dp[N][N]; int C[N][N]; int q[N]; void add(int &u, int v){ u = (u + v) % MOD; } int mm[2][10]; int fac[M]; int yo[N][N]; int oo[N]; ll brute(int n, int m){ vector<pii> P; for(int i = 1; i <= n; i ++ ){ P.push_back(mp(i, 0)); P.push_back(mp(i, 1)); } int soln = 0; bool ss; int cc; do{ for(int i = 0 ; i < P.size(); i ++ ){ mm[P[i].se][P[i].fi] = i % m; } ss = true; for(int i = 1; i <= n; i ++ ){ if(mm[0][i] == mm[1][i]) ss = false; oo[i] = 0; } if(ss){ for(int i = 0 ; i < m; i ++ ){ for(int j = i ; j < 2 * n; j += m){ oo[P[j].fi] ++ ; } cc = 0; for(int j = 1; j <= n; j ++ ){ if(oo[j] == 1) cc ++ ; } yo[i][cc] ++ ; } } if(ss) soln ++ ; }while(next_permutation(P.begin(), P.end())); return soln; } int main(){ fastIO; //freopen("in.txt","r",stdin); int n, m; cin >> n >> m; fac[0]=1; for(int i = 0 ; i <= n; i ++ ){ C[i][0] = 1; } for(int i = 1; i <= n * 2; i ++ ){ fac[i] = (fac[i - 1] * 1ll * i) % MOD; } for(int i = 0; i < n * 2; i ++ ){ q[i % m] ++ ; } for(int i = 1; i <= n; i ++ ){ for(int j = 1; j <= i; j ++ ){ C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } } dp[0][q[0]] = (C[n][q[0]] * 1ll * fac[q[0]]); int qs = 0; ll V, U; int full; for(int i = 1; i < m ; i ++ ){ qs += q[i - 1]; for(int x = 0; x <= n; x ++ ){ if(dp[i-1][x] == 0) continue; for(int y = 0; y <= x && y <= q[i]; y ++ ){ V = C[x][y]; full = n - (qs - x) / 2 - x; U = C[full][q[i] - y]; U = (U * 1ll * V) % MOD; U = (U * 1ll * fac[q[i]]) % MOD; U = (U * 1ll * dp[i-1][x]) % MOD; add(dp[i][(x - y) + (q[i] - y)], U); } } } ll pwr = 1ll; for(int i = 1; i <= n; i ++ ){ pwr = (pwr * 2ll) % MOD; } ll res = (dp[m - 1][0] * 1ll * pwr) % MOD; cout << res << "\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'll brute(int, int)':
Main.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0 ; i < P.size(); i ++ ){
      |                         ~~^~~~~~~~~~
#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...