Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <math.h>
- #include <bits/stdc++.h>
- using namespace std;
- #define FOR(i,a,b) for(int i=(a);i<(b);++i)
- #define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
- #define FILL(A,val) memset(A,val,sizeof(A))
- #define ITER(it,a) for(__typeof(a.begin()) it=a.begin();it!=a.end();++it)
- #define DBG1(a) cerr<<#a<<"="<<(a)<<"\n"
- #define DBG2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
- #define ALL(V) V.begin(),V.end()
- #define SZ(V) (int)V.size()
- #define PB push_back
- #define MP make_pair
- typedef long long LL;
- typedef unsigned long long ULL;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- const double PI = acos(-1.0);
- const int INF = 1000*1000*1000 + 7;
- const LL LINF = 1LL*INF*INF;
- const int MAX = 222;
- const LL MOD = 1000000007;
- LL dp[MAX][2][MAX];
- LL dpPr[MAX][MAX];
- LL dpSuf[MAX][MAX];
- LL temp[MAX];
- int sz[MAX];
- VI g[MAX];
- int K;
- LL C[MAX][MAX];
- LL H(int n,int m)
- {
- //TODO
- }
- void dfsSz(int v)
- {
- sz[v] = 1;
- FOR(i,0,SZ(g[v]))
- {
- int to = g[v][i];
- dfs(to);
- sz[v] += sz[to];
- }
- }
- void dfs(int v)
- {
- if(sz[v]==1)
- {
- dp[v][0][0]=1;
- return ;
- }
- int sumSz = 0;
- FOR(i,0,SZ(g[v]))
- {
- int to = g[v][i];
- dfs(to);
- if(i==0)
- {
- FOR(k,0,K+1)
- dp[v][0][k] = (dp[to][0][k] + dp[to][1][k]);
- }
- else
- {
- RFOR(kmy,K+1,0)
- FOR(k,0,kmy+1)
- {
- dp[v][0][kmy]+=((dp[v][0][kmy-k]*(dp[to][0][k]+dp[to][1][k]))%MOD) *H(sumSz+1,sz[to])%MOD;
- dp[v][0][kmy]%=MOD;
- }
- }
- FOR(k,0,K+1)
- dpPr[i][k] = dp[v][0][k];
- sumSz+=sz[to];
- }
- sumSz = 0;
- RFOR(i,SZ(g[v]),0)
- {
- int to = g[v][i];
- dfs(to);
- if(i==SZ(g[v])-1)
- {
- FOR(k,0,K+1)
- dp[v][0][k] = (dp[to][0][k] + dp[to][1][k]);
- }
- else
- {
- RFOR(kmy,K+1,0)
- FOR(k,0,kmy+1)
- {
- dp[v][0][kmy]+=((dp[v][0][kmy-k]*(dp[to][0][k]+dp[to][1][k]))%MOD) *H(sumSz+1,sz[to])%MOD;
- dp[v][0][kmy]%=MOD;
- }
- }
- FOR(k,0,K+1)
- dpSuf[i][k] = dp[v][0][k];
- sumSz+=sz[to];
- }
- FOR(i,0,SZ(g[v]))
- {
- int to = g[v][i];
- FILL(temp,0);
- FOR(k,0,K+1)
- FOR(k2,0,k+1)
- {
- LL l = 1;
- if(i) l = dpPr[i-1][k2];
- LL r = 1;
- if(i+1<SZ(g[v]))r = dpSuf[i+1][k-k2];
- temp[k] = (temp[k] + l*r)%MOD;
- }
- FOR(k,0,K+1)
- {
- dp[v][1][k] = 0;
- FOR(k1,1,k+1)
- {
- dp[v][1][k] = (dp[v][1][k] + temp[k-k1] * dp[to][0][k1-1])%MOD;
- }
- }
- }
- }
- int main()
- {
- //freopen("in.txt","r",stdin);
- ios::sync_with_stdio(false);cin.tie(0);
- int m;
- while(true)
- {
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement