VK cup 2017 E. Singer House （奇妙的dp）_550384565

VK cup 2017 E. Singer House

time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
It is known that passages in Singer house are complex and intertwined. Let’s define a Singer k-house as a graph built by the following process: take complete binary tree of height k and add edges from each vertex to all its successors, if they are not yet present.

Singer 4-house

Count the number of non-empty paths in Singer k-house which do not pass the same vertex twice. Two paths are distinct if the sets or the orders of visited vertices are different. Since the answer can be large, output it modulo 109 + 7.

Input
The only line contains single integer k (1 ≤ k ≤ 400).

Output
Print single integer — the answer for the task modulo 109 + 7.

Examples

input
2
output
9

input
3
output
245

input
20
output
550384565

Note
There are 9 paths in the first example (the vertices are numbered on the picture below): 1, 2, 3, 1-2, 2-1, 1-3, 3-1, 2-1-3, 3-1-2.

中文题目

思路：

比如样例解释中给的1,2,3的图，f[2][1] = 9;(1; 2; 3; 1->2; 2->1; 1->3; 3->1; 2->1->3; 3->1->2); f[2][2] = 7;(2,1->3; 2,3->1; 3,1->2; 3,2->1; 1,2; 1,3; 2,3;); f[3][3] = 1;(1,2,3);
这样的话题解应该就容易理解了。
吐槽一下：什么鬼题呀！什么鬼状态呀！谁考试想得到！！！
好吧，还是低估大佬的能耐了%%%

#include <cstdio>
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;

const int N = 810;
int mod, n;
LL f[N][N];

int main(){
    freopen ("tree.in", "r", stdin);
    freopen ("tree.out", "w", stdout);
    scanf("%d%d", &n, &mod);
    f[1][1] = 1; f[1][0] = 1;
    for(register int i=2; i<=n; i++){
        int lim;
        if(i <= 10) lim = min((1<<i)-1, n-i+2);
        else lim = n-i+2;//要爆int 
        //cout << lim << endl;
        for(register int l=0; l<=lim; l++)
            for(register int r=0; l+r-1<=lim; r++){
                LL num = 1ll * f[i-1][l] * f[i-1][r] % mod;
                f[i][l+r] = (f[i][l+r] + num) % mod;
                f[i][l+r+1] = (f[i][l+r+1] + num) % mod;
                f[i][l+r] = (f[i][l+r] + 2ll * num * l % mod) % mod;
                f[i][l+r] = (f[i][l+r] + 2ll * num * r % mod) % mod;
                //connect two
                f[i][l+r-1] = (f[i][l+r-1] + 2ll * l * r % mod * num % mod) % mod;
                //connect single
                f[i][l+r-1] = (f[i][l+r-1] + 1ll * l * (l-1) % mod * num % mod) % mod;
                f[i][l+r-1] = (f[i][l+r-1] + 1ll * r * (r-1) % mod * num % mod) % mod;
            }
    }
    if(n == 1) return cout << '0' << endl, 0;//特判 
    cout << f[n][1] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39