Submission #1049167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049167		underwaterkillerwhale	NoM (RMI21_nom)	C++17	100 / 100	140 ms	79908 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];
int dp[N][2 * N];
int fac[2 * N], C[2 * N][2 * N];
int pre[N];

inline void add (int &A, int B) { A += B; if (A > Mod) A -= Mod; }

void solution () {
    cin >> n >> m;

    fac[0] = 1;
    rep (i, 1, 2 * n) fac[i] = 1LL * fac[i - 1] * i % Mod;
    rep (i, 0, 2 * n)
    rep (j, 0, i) {
        if (j == 0 || j == i) C[j][i] = 1;
        else C[j][i] = C[j][i - 1] + C[j - 1][i - 1];
        if (C[j][i] > Mod) C[j][i] -= Mod;
    }
//    cout << C[8][23] <<"\n";
    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];
    }
    dp[0][0] = 1;
    rep (i, 0, m)
    rep (j, 0, pre[i]) {
        int pw2 = 1;
        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) >> 1);
                int remcol = n - (pcol - x);
                if (remcol >= 0)
                add (dp[i + 1][nj], 1LL * 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] % Mod * pw2 % Mod);
            }
            pw2 = 1LL * pw2 * 2 % Mod;
        }
//        cout << i<<","<<j<<" "<<dp[i][j] <<"\n";
    }

    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: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48