看了数据范围我甚至想用佛洛依德。。。。。。，但最后还是嫌麻烦用了深搜，居然有点快0.5s了，囧~

记得开五十万数据.........................................
数据范围害死人................

不知道大家怎么做的，我花了一个小时想算法，后来写了个爆搜找规律。
f[i][j]=f[i-1][j]*j+f[i-1][j-1]*(i+1-j);
后来还是0分，文件名写错了。

表示记忆化搜秒杀一切DP

并查集+tarjan求强连通+特殊处理的spfa

遍历，小优化

简单动归，蛋疼的是开longint会爆- -！ 囧~
dp[i,j]表示前i个有j个上升序列的个数，方程dp[i,j]:=dp[i-1,j-1]*(i-j+1)+dp[a-1,b]*b ，意思是要转移成当前状态需要两种状态转移过来，分别对应加上当前数后序列个数增加和不增加两种情况，边界值dp[i,1]:=1,i∈[1,n].

@Makazeu 自己动手，丰衣足食

如果暴力枚举的话，算出n=20的情况需要15000年

没有插件的话，，这题怎么写？

s在扯淡无误，话说变量名打错居然还能40分，rp总在无意中流失啊~，钱的总量和物品价值还是刚开始就除以10好了，

2L 大神装弱菜。rp会掉，怒捡！

由于前一天比赛的原因，我还是写了高精度。。。应该先验证一下要不要写的。。。

背包问题是没问题，不过还是处理的复杂了，m 只有 60 还是很小的嘛。s 根本是在扯淡。

BFS状态最多2^15-1种，秒之

从10X10的表找规律，
然后每个程序现场打表（好浪费……），再输出

比赛时先写了个单向的bfs，后面又写了个双向的，结果双向的wa了一个点而单向的却AC了

上午的打开O2优化过了
下午的不开O2优化过了
方法是一样的：泛化背包
优化处理：
1、数组降维。减少不必要的循环次数。
2、并不是把所有的背包都当做泛化背包，生成泛化函数，而是仅把有附件的背包泛化处理。

先用 STL 枚举出来一个表（算到 n=12 就出不来了）

1: 1
2: 1 1
3: 1 4 1
4: 1 11 11 1
5: 1 26 66 26 1
6: 1 57 302 302 57 1
7: 1 120 1191 2416 1191 120 1
8: 1 247 4293 15619 15619 4293 247 1
9: 1 502 14608 88234 156190 88234 14608 502 1
10: 1 1013 47840 455192 1310354 1310354 455192 47840 1013 1
11: 1 2036 152637 2203488 9738114 15724248 9738114 2203488 152637 2036 1
12: 1 4083 478271 10187685 66318474 162512286 162512286 66318474 10187685 478271 4083 1

然后找规律 \[ f_{i, j} = (i - j + 1) \times f_{i-1, j-1} + j \times f_{i-1, j} \] 要用 long long ，高精度暂时不必～

先暴力next_permutation，然后递推。