Submission #703357

#	Time	Username	Problem	Language	Result	Execution time	Memory
703357		Nursik	NoM (RMI21_nom)	C++14	52 / 100	1074 ms	16944 KiB

Main

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 2e3 + 10, maxm = 1e7 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int is[maxn];
ll fact[maxn * 2];
ll dp[maxn][maxn];
ll bp(ll a, ll n){
    ll res = 1;
    while (n > 0){
        if (n & 1)
            res *= a;
        a *= a, n >>= 1;
        res %= mod, a %= mod;
    }
    return res;
}

ll cnk(int n, int k){
    return fact[n] * bp(fact[k], mod - 2) % mod * bp(fact[n - k], mod - 2) % mod;
}
int n, m;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   // freopen("paths.in", "r", stdin);
   // freopen("paths.out", "w", stdout);
    cin >> n >> m;
    fact[0] = 1;
    for (int i = 1; i <= n * 2; ++i){
        fact[i] = fact[i - 1] * i % mod;
        int z = i % m + 1;
        is[z] += 1;
    }
    dp[0][0] = 1;
    for (int i = 1; i <= m; ++i){
        for (int j = 0; j <= n; ++j){
            if (dp[i - 1][j] > 0){
                for (int k = 0; k * 2 <= is[i]; ++k){
                    if (j + k <= n){
                        dp[i][j + k] = (dp[i][j + k] + dp[i - 1][j] * cnk(j + k, k) % mod * fact[is[i]] % mod * bp(fact[is[i] - 2 * k], mod - 2) % mod) % mod;
                    }
                    else{
                        break;
                    }
                }
            }
            else{
                break;
            }
        }
    }
    ll ans = fact[2 * n];
    int cur = 1;
    //cout << ans << '\n';
    for (int i = 1; i <= n; ++i){
        ll del = cur * cnk(n, i) % mod  * fact[2 * n - 2 * i] % mod * dp[m][i] % mod;
        cur *= -1;
        ans = (ans - del + mod) % mod;
    }
    cout << ans;
}
/*
*/

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