Submission #643392

#	Time	Username	Problem	Language	Result	Execution time	Memory
643392		danikoynov	NoM (RMI21_nom)	C++14	100 / 100	220 ms	63196 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2010;
const ll mod = 1e9 + 7;
int n, m;
ll dp[maxn][maxn], ch[maxn][maxn], t[maxn], f[maxn];
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        int cnt = (2 * n - i) / m + 1;
        t[i] = cnt;

    }

    for (int i = 0; i <= max(n, m); i ++)
        ch[i][0] = 1;

    for (int i = 1; i <= max(n, m); i ++)
        for (int j = 1; j <= max(n, m); j ++)
        {
            ch[i][j] = ch[i - 1][j - 1] + ch[i - 1][j];
            if (ch[i][j] >= mod)
                ch[i][j] -= mod;
        }

    f[0] = 1;
    for (ll i = 1; i <= (ll)max(n, m); i ++)
    {
        f[i] = (f[i - 1] * i) % mod;
    }
    dp[0][0] = 1;
    for (int i = 0; i < m; i ++)
        for (int j = 0; j <= n; j ++)
        {
            for (int k = max((ll)(0), t[i + 1] - j); k <= t[i + 1]; k ++)
            {
                dp[i + 1][j + k - (t[i + 1] - k)] += (((((dp[i][j] * ch[j][t[i + 1] - k]) % mod) * ch[t[i + 1]][t[i + 1] - k]) % mod) * f[t[i + 1] - k]) % mod;
                ///cout << i << " " << j << " " << k << " " << i + 1 << " " << j + k - (t[i + 1] - k) << endl;
                if (dp[i + 1][j + k - (t[i + 1] - k)] >= mod)
                    dp[i + 1][j + k - (t[i + 1] - k)] -= mod;
            }
            ///cout << dp[i][j] << " ";
        }
    ///cout << dp[m][0] << endl;
    ll ans = dp[m][0];
    for (ll i = 1; i <= n; i ++)
        ans = (((ans * i) % mod) * (ll)(2)) % mod;


    cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}

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