?
# | 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 |
// 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; }
?
?
?
?