oj.uz

Submission #1049146

# Submission time Handle Problem Language Result Execution time Memory
1049146 2024-08-08T14:03:49 Z underwaterkillerwhale NoM (RMI21_nom) C++17
9 / 100
 37 ms 608 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 37 ms 608 KB Output is correct
12 Correct 19 ms 604 KB Output is correct
13 Incorrect 10 ms 488 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 37 ms 608 KB Output is correct
12 Correct 19 ms 604 KB Output is correct
13 Incorrect 10 ms 488 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 37 ms 608 KB Output is correct
12 Correct 19 ms 604 KB Output is correct
13 Incorrect 10 ms 488 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 37 ms 608 KB Output is correct
12 Correct 19 ms 604 KB Output is correct
13 Incorrect 10 ms 488 KB Output isn't correct
14 Halted 0 ms 0 KB -