General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
252391101 Practice:
DisconnectedGraph
724F - 16 C++17 (GCC 7-32) Accepted 951 ms 47480 KB 2024-03-20 07:38:28 2024-03-20 07:38:28
→ Source
// LUOGU_RID: 151749030
#include <bits/stdc++.h>
using namespace std;
#define _rep(i_,a_,b_) for(int i_ = (a_); i_ <= (b_); ++i_)
#define mid ((L+R) >> 1)
#define multiCase() int testCnt = in(); _rep(curCase,1,testCnt)
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
using ll = long long;
using pii = pair<int,int>;

int in(void) { int x; scanf("%d", &x); return x; } ll inl(void) { ll x; scanf("%lld", &x); return x; }
void out(int x) { printf("%d ", x); } void outln(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld ", x); } void outln(ll x) { printf("%lld\n", x); }
template<typename T> void chkmax(T &a, const T &b) { a = max(a, b); } 
template<typename T> void chkmin(T &a, const T &b) { a = min(a, b); } 
int n = in(), d = in(), p = in();
const int kN = 1050;
int f[kN][11][kN], iv[kN];
int C(int n, int m) {
	n %= p;
	int res = 1;
	_rep(i,n - m + 1,n) res = 1ll * res * i % p;
	res = 1ll * res * iv[m] % p;
	return res;
}
int main() {
	iv[1] = 1; _rep(i,2,n) iv[i] = 1ll * iv[p % i] * (p - p / i) % p;
	iv[0] = 1; _rep(i,1,n) iv[i] = 1ll * iv[i] * iv[i - 1] % p;
	if(n == 1 || n == 2) {
		puts("1");
		return 0;
	}
	_rep(j,0,n) f[1][0][j] = 1;
	_rep(i,2,n) _rep(j,1,d) _rep(k,1,n) {
		_rep(l,0,j) {
			if(l * k > i) break;
			if(k > 1) f[i][j][k] = (f[i][j][k] + 1ll * f[i - l * k][j - l][k - 1] * C(f[k][d - 1][k] + l - 1, l)) % p;
			else f[i][j][k] = (f[i][j][k] + 1ll * f[i - l * k][j - l][k - 1] * C(f[k][0][k] + l - 1, l)) % p;
		}
		debug("f[%d][%d][%d] = %d\n", i, j, k, f[i][j][k]);
	}
	if(n & 1) outln(f[n][d][n / 2]);
	else outln((f[n][d][n / 2] - C(f[n / 2][d - 1][n / 2], 2) + p) % p);
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details