Advertisement
Guest User

Untitled

a guest
Sep 29th, 2016
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7.  
  8. #define FOR(i,a,b) for(int i=(a);i<(b);++i)
  9. #define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
  10. #define FILL(A,val) memset(A,val,sizeof(A))
  11. #define ITER(it,a) for(__typeof(a.begin()) it=a.begin();it!=a.end();++it)
  12. #define DBG1(a) cerr<<#a<<"="<<(a)<<"\n"
  13. #define DBG2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  14.  
  15. #define ALL(V) V.begin(),V.end()
  16. #define SZ(V) (int)V.size()
  17. #define PB push_back
  18. #define MP make_pair
  19.  
  20. typedef long long LL;
  21. typedef unsigned long long ULL;
  22. typedef vector<int> VI;
  23. typedef pair<int, int> PII;
  24.  
  25. const double PI = acos(-1.0);
  26. const int INF = 1000*1000*1000 + 7;
  27. const LL LINF = 1LL*INF*INF;
  28.  
  29. const int MAX = 222;
  30. const LL MOD = 1000000007;
  31.  
  32. LL dp[MAX][2][MAX];
  33. LL dpPr[MAX][MAX];
  34. LL dpSuf[MAX][MAX];
  35. LL temp[MAX];
  36. int sz[MAX];
  37.  
  38. VI g[MAX];
  39.  
  40. int K;
  41.  
  42. LL C[MAX][MAX];
  43. LL H(int n,int m)
  44. {
  45.     //TODO
  46. }
  47.  
  48. void dfsSz(int v)
  49. {
  50.     sz[v] = 1;
  51.     FOR(i,0,SZ(g[v]))
  52.     {
  53.         int to = g[v][i];
  54.         dfs(to);
  55.         sz[v] += sz[to];
  56.     }
  57. }
  58.  
  59. void dfs(int v)
  60. {
  61.     if(sz[v]==1)
  62.     {
  63.         dp[v][0][0]=1;
  64.         return ;
  65.     }
  66.    
  67.     int sumSz = 0;
  68.     FOR(i,0,SZ(g[v]))
  69.     {
  70.         int to = g[v][i];
  71.        
  72.         dfs(to);
  73.        
  74.         if(i==0)
  75.         {
  76.             FOR(k,0,K+1)
  77.                 dp[v][0][k] = (dp[to][0][k] + dp[to][1][k]);
  78.         }
  79.         else
  80.         {
  81.             RFOR(kmy,K+1,0)
  82.             FOR(k,0,kmy+1)
  83.             {
  84.                 dp[v][0][kmy]+=((dp[v][0][kmy-k]*(dp[to][0][k]+dp[to][1][k]))%MOD) *H(sumSz+1,sz[to])%MOD;
  85.                 dp[v][0][kmy]%=MOD;
  86.             }
  87.         }
  88.        
  89.         FOR(k,0,K+1)
  90.             dpPr[i][k] = dp[v][0][k];
  91.        
  92.         sumSz+=sz[to];
  93.     }
  94.    
  95.     sumSz = 0;
  96.    
  97.     RFOR(i,SZ(g[v]),0)
  98.     {
  99.         int to = g[v][i];
  100.        
  101.         dfs(to);
  102.        
  103.         if(i==SZ(g[v])-1)
  104.         {
  105.             FOR(k,0,K+1)
  106.                 dp[v][0][k] = (dp[to][0][k] + dp[to][1][k]);
  107.         }
  108.         else
  109.         {
  110.             RFOR(kmy,K+1,0)
  111.             FOR(k,0,kmy+1)
  112.             {
  113.                 dp[v][0][kmy]+=((dp[v][0][kmy-k]*(dp[to][0][k]+dp[to][1][k]))%MOD) *H(sumSz+1,sz[to])%MOD;
  114.                 dp[v][0][kmy]%=MOD;
  115.             }
  116.         }
  117.        
  118.         FOR(k,0,K+1)
  119.             dpSuf[i][k] = dp[v][0][k];
  120.        
  121.         sumSz+=sz[to];
  122.     }
  123.    
  124.    
  125.     FOR(i,0,SZ(g[v]))
  126.     {
  127.         int to = g[v][i];
  128.         FILL(temp,0);
  129.         FOR(k,0,K+1)
  130.             FOR(k2,0,k+1)
  131.             {
  132.                 LL l = 1;
  133.                 if(i) l = dpPr[i-1][k2];
  134.                 LL r = 1;
  135.                 if(i+1<SZ(g[v]))r = dpSuf[i+1][k-k2];
  136.                
  137.                 temp[k] = (temp[k] + l*r)%MOD;
  138.             }
  139.        
  140.         FOR(k,0,K+1)
  141.         {
  142.             dp[v][1][k] = 0;
  143.             FOR(k1,1,k+1)
  144.             {
  145.                 dp[v][1][k] = (dp[v][1][k] + temp[k-k1] * dp[to][0][k1-1])%MOD;
  146.             }
  147.         }
  148.     }
  149. }
  150.  
  151. int main()
  152. {
  153.     //freopen("in.txt","r",stdin);
  154.     ios::sync_with_stdio(false);cin.tie(0);
  155.    
  156.     int m;
  157.     while(true)
  158.     {
  159.    
  160.        
  161.     }
  162.    
  163.     return 0;
  164. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement