1、给出只包含'(',')','[',']'的字符串$s$，删除一些字符，使得剩下的是合法的括号。有多少种删除方法？ $|s|\leq 40$
思路：左括号和右括号较少的一种不会大于20。假设左括号少。设$f[i][mask][k]$表示处理了前$i$个字符，其中留下的字符以$k$开头（$k=0$表示'(',$k=1$表示'['），且所有留下的字符状态为$mask$，（$mask$的最高位为1，其他位为0表示另一种括号，否则表示跟最高位相同的符号）。
#include#include #include #include #include #include #include
2、给定$n,m$，$n$个数字的排列有$n!$种，设其中某一种为$P_{i}$，设$P_{i}$中循环的个数$f(P_{i})=t_{i}$,那么$P_{i}$对答案的贡献为$t_{i}^{m}$。设所有排列的集合为$S$，计算$\sum_{P_{i}\in S}f(P_{i})^{m}$。$1\leq n\leq 100000,0\leq m\leq 300$
思路：给出一些定义：
（1）第一类斯特灵数:$s(n,k)$，表示将$n$个元素排列成$k$个轮换的个数，递推公式:$s(n,k)=(n-1)s(n-1,k)+s(n-1,k-1),n>0$
（2）第二类斯特灵数:$S(n,k)$，表示将$n$个元素分成$k$个非空集合的方案数，递推公式:$S(n,k)=k*S(n-1,k)+S(n-1,k-1),n>0$
（3）$x^{n}=\sum_{k=0}^{n}S(n,k)x(x-1)...(x-k+1),n\geq 0$.这个可以用数学归纳法证明。
（4）$x(x+1)...(x+n-1)=\sum_{k=0}^{n}s(n,k)x^{k},n\geq 0$.这个可以用数学归纳法证明。
==========分隔符=========
现在回到题目。需要求的是$ans=\sum_{k=0}^{n}s(n,k)k^{m}$，借助上面第（3）个公式得到：
$ans=\sum_{k=0}^{n}s(n,k)k^{m}$
$=\sum_{k=0}^{n}s(n,k)\sum_{t=0}^{m}S(m,t)k(k-1)...(k-t+1)$
$=\sum_{t=0}^{m}S(m,t)\sum_{k=0}^{n}s(n,k)k(k-1)...(k-t+1)$
现在考虑 $\sum_{k=0}^{n}s(n,k)k(k-1)...(k-t+1)$
对公式（4）两端求$t$阶导数得到：$(x(x+1)...(x+n-1))^{(t)}=\sum_{k=0}^{n}s(n,k)k(k-1)...(k-t+1)x^{k-t}$.
如果令$x=1$就得到了$\sum_{k=0}^{n}s(n,k)k(k-1)...(k-t+1)$。
现在就是需要计算$(x(x+1)...(x+n-1))^{(t)}_{x=1}$的值。
令$u=x-1$，那么就是求$((u+1)(u+2)...(u+n))^{(t)}_{u=0}$的值。
$(u+1)(u+2)...(u+n)=a_{n,0}+a_{n,1}u+...+a_{n,t}u^{t}+...+a_{n,n}u^{n}$
现在只需要计算出$a_{n,t}$即可，那么$\sum_{k=0}^{n}s(n,k)k(k-1)...(k-t+1)=a_{n,t}*t!$
下面用数学归纳法证明:$a_{n,t}=s(n+1,t+1)$.
（1）假设$t$固定，小于等于$n-1$时均成立；即$a_{n-1,t}=s(n,t+1)$.
（2）对于$(u+1)(u+2)...(u+n)中$中$u_{t}$的系数的所有项是由$n$项中选出$n-t$项的乘积组成的。那么如果某一项乘积包含$n$时，就是$n*a_{n-1,t}=n*s(n,t+1)$；如果不包含$n$，那么就是由$[1,n-1]$中任意选出$n-t$项，这其实就是$a_{n-1,t-1}=s(n,t)$。
所以$(u+1)(u+2)...(u+n-1)$中$u_{t}$的系数$a_{n,t}=n*s(n,t+1)+s(n,t)=s(n+1,t+1)$.
#include#include #include #include #include #include #include