Submission #1049146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049146		underwaterkillerwhale	NoM (RMI21_nom)	C++17	9 / 100	37 ms	608 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e3 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll BASE = 137;

int n, m;
int h[N];
ll dp[N][N];
ll fac[2 * N];
int pre[N];

ll power (int n, int m) {
    if (m == 0) return 1;
    ll t = power (n, m >> 1);
    (t *= t) %= Mod;
    if (m & 1) return n * t % Mod;
    else return t;
}

ll C (int r, int n) {
    if (r > n) return 0;
    return fac[n] * power (fac[r], Mod - 2) % Mod * power (fac[n - r], Mod - 2) % Mod;
}

void solution () {

    cin >> n >> m;
    fac[0] = 1;
    rep (i, 1, 2 * n) fac[i] = fac[i - 1] * i % Mod;
    rep (i, 0, 2 * n - 1) {
        h[i % m + 1]++;
    }
//    vector<pair<int,int>> vec;
//    rep (j, 0, 1)
//    rep (i, 1, n) vec.push_back({i, j});
//    sort (ALL(vec));
//    ll res = 0;
//    do {
//        int ok = 1;
//        rep (i, 0, 2 * n - 1) if (i >= m  && vec[i].fs == vec[i - m].fs) ok = 0;
//        res += ok;
//        if (ok) {
//            iter (&id, vec) cout << id.fs<<","<<id.se <<" ";
//            cout<<"\n";
//        }
//    }while(next_permutation(ALL(vec)));
//    cout << res <<"\n";
    rep (i, 1, m) {
        pre[i] = pre[i - 1] + h[i];
//        cout << h[i] <<" ";
    }
//    cout<<"\n";
    dp[1][h[1]] = C(h[1], n) * fac[h[1]] % Mod * power(2, h[1]) % Mod;
//    cout <<h[1] <<" "<<dp[1][h[1]] <<"\n";
    rep (i, 1, m)
    rep (j, 0, 2 * n) {
        rep (x, 0, h[i + 1]) {
            int nj = j + 2 * x - h[i + 1];
            if (nj >= 0 && nj <= 2 * n) {
                int pcol = nj + (pre[i + 1] - nj) / 2;
                int remcol = n - (pcol - x);
                (dp[i + 1][nj] += dp[i][j] * C(h[i + 1] - x, j) % Mod * C (x, h[i + 1]) % Mod * C(x, remcol) % Mod * fac[x] % Mod * fac[h[i + 1] - x] * power(2, x) % Mod) %= Mod;
//                if (nj == 2) cout << x <<" "<<nj<<" "<<remcol<<" aaa\n";
            }
//            if (j == 2 && x == 0) cout << dp[i - 1][j] <<"hihi "<<dp[i][j + 2 * x - h[i]]<<"\n";
        }
//        cout << i<<","<<j<<" "<<dp[i][j] <<"\n";
    }
//    cout << dp[2][2] <<"\n";
//    return;
    cout << dp[m][0] <<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9

*/

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 18
• Subtask 5: 0 / 48