Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) F - Uniformly Branched Trees 无根树->有根树+dp

时间：2022-10-22 07:33:54

F - Uniformly Branched Trees

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 1e3 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

LL dp[N][][N], inv[N], f[N], finv[N], g[N][];

int n, d, mod;

void init() {

    inv[] = f[] = finv[] = ;

    for(int i = ; i < N; i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;

    for(int i = ; i < N; i++) f[i] = f[i-]*i%mod;

    for(int i = ; i < N; i++) finv[i] = finv[i-]*inv[i]%mod;

}

int main() {

    scanf("%d%d%d", &n, &d, &mod);

    init();

    for(int i = ; i <= n; i++) dp[][][i] = ;

    for(int i = ; i <= d; i++) g[][i] = ;

    for(int i = ; i <= n; i++) {

        for(int j = ; j <= d; j++) {

            for(int k = ; k < i; k++) {

                for(int l = ; l <= j && l*k <= i; l++) {

                    dp[i][j][k] = (dp[i][j][k] + 1ll*dp[i-l*k][j-l][k-]*g[k][l])%mod;

                }

            }

            for(int k = ; k <= n; k++) dp[i][j][k] = (dp[i][j][k]+dp[i][j][k-])%mod;

        }

        g[i][] = dp[i][d-][n];

        for(int j = ; j <= d; j++)

            g[i][j] = g[i][j-]*(dp[i][d-][n]+j-)%mod*inv[j]%mod;

    }

    LL ans = ;

    if(n <= ) ans = ;

    else ans = dp[n][d][n/];

    if(n >  && !(n&)) {

        ans = (ans + mod - dp[n/][d-][n/] * (dp[n/][d-][n/]-) /  % mod) % mod;

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/

相关文章