Submission #703376

#	Time	Username	Problem	Language	Result	Execution time	Memory
703376		Nursik	NoM (RMI21_nom)	C++14	100 / 100	68 ms	27972 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];
int fact[maxn * 2], rfact[maxn * 2];
int c[maxn][maxn];
int dp[maxn][maxn];
int 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;
}
inline void add(int& x, int y){
    x += y;
    if (x >= mod)
        x -= mod;
    x %= 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;
    rfact[0] = 1;
    for (int i = 1; i <= n * 2; ++i){
        fact[i] = fact[i - 1] * 1ll * i % mod;
        int z = i % m + 1;
        is[z] += 1;
        rfact[i] = bp(fact[i], mod - 2);
    }
    for (int i = 0; i <= n; ++i){
        c[i][0] = 1;
        c[i][i] = 1;
        for (int j = 1; j < i; ++j){
            int x = c[i - 1][j], y = c[i - 1][j - 1];
            add(c[i][j], c[i - 1][j]);
            add(c[i][j], c[i - 1][j - 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){
                        int x = (dp[i - 1][j] * 1ll * c[j + k][k] % mod * fact[is[i]] % mod * rfact[is[i] - 2 * k] % mod);
                        add(dp[i][j + k], x);
                    }
                    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 * c[n][i] % mod  * fact[2 * n - 2 * i] % mod * dp[m][i] % mod;
        cur *= -1;
       // cout << c[n][i] << " " << fact[2 * n - 2 * i] << " " << dp[m][i] << '\n';
        ans = (ans - del + mod) % mod;
    }
    cout << ans;
}
/*
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:84:17: warning: unused variable 'x' [-Wunused-variable]
   84 |             int x = c[i - 1][j], y = c[i - 1][j - 1];
      |                 ^
Main.cpp:84:34: warning: unused variable 'y' [-Wunused-variable]
   84 |             int x = c[i - 1][j], y = c[i - 1][j - 1];
      |                                  ^

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