Submission #44863

#	Time	Username	Problem	Language	Result	Execution time	Memory
44863		PowerOfNinjaGo	Asceticism (JOI18_asceticism)	C++17	49 / 100	84 ms	56064 KiB

asceticism

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int md = 1e9+7;
void add(int &a, int b)
{
    a += b;
    if(a>= md) a-= md;
}
int mul(int a, int b)
{
    return (1LL*a*b)%md;
}
const int maxn = 3e3+5;
int dp[maxn][maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    dp[1][0] = 1;
    for(int i = 2; i<= n; i++)
    {
        for(int j = 0; j< i; j++)
        {
            dp[i][j] = mul(j+1, dp[i-1][j]);
            add(dp[i][j], mul(i-j, dp[i-1][j-1]));
            //printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
        }
    }
    cout << dp[n][k-1] << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51