Submission #540132

#TimeUsernameProblemLanguageResultExecution timeMemory
540132dooweyNoM (RMI21_nom)C++14
9 / 100
1085 ms1084 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 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]; 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; 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; } 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; for(int i = 0 ; i <= n; i ++ ){ C[i][0] = 1; } 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]]; 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; U = C[full][q[i] - y]; U = (U * 1ll * V) % 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 << brute(n, m) << "\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'll brute(int, int)':
Main.cpp:34: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]
   34 |         for(int i = 0 ; i < P.size(); i ++ ){
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:84:8: warning: unused variable 'res' [-Wunused-variable]
   84 |     ll res = (dp[m - 1][0] * 1ll * pwr) % MOD;
      |        ^~~
#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...