Submission #368195

#	Time	Username	Problem	Language	Result	Execution time	Memory
368195		rqi	Asceticism (JOI18_asceticism)	C++14	49 / 100	1091 ms	71148 KiB

asceticism

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1e9+7;

const int mx = 3005;

struct mi{
	ll v;
	mi(){
		v = 0;
	}
	mi(ll _v){
		v = _v % MOD;
	}
};

mi& operator+=(mi& a, mi b){
	a.v+=b.v;
	if(a.v >= MOD) a.v-=MOD;
	return a;
}

mi operator+(mi a, mi b){
	a+=b;
	return a;
}

mi operator*(mi a, mi b){
	a.v = (a.v*b.v) % MOD;
	return a;
}

mi dp[mx][mx];

int main(){
	int N, K;
	cin >> N >> K;

	dp[0][0] = mi(1);

	for(int i = 0; i <= N+2; i++){
		for(int j = 0; j <= N+2; j++){
			dp[i][j+1]+=mi(i+1)*dp[i][j];
			dp[i+1][j]+=mi(j+1)*dp[i][j];
		}
	}

	cout << dp[N-K][K-1].v << "\n";

}

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