$\newcommand{stirf}[2]{

{

{#1}\brack{#2}}}$$\newcommand{stirs}[2]{

{

{#1}\brace{#2}}}$题意：$\sum\limits_{i=1}^mx_i\leq s$，对$\forall1\leq i\leq n,x_i\leq t$，求这个方程组的解数

做了几天总算是弄明白了...

会用到$\sum\limits_{k\leq n}\binom km=\binom{n+1}{m+1}$，这个直接归纳可证

方程$\sum\limits_{i=1}^nx_i=s,x_i\geq1$的解数是$\binom{s-1}{n-1}$，所以$\sum\limits_{i=1}^nx_i\leq s,x_i\geq1$的解数是$\binom sn$

枚举$x_{1\cdots n}$，答案即为$\sum\limits_{1\leq x_1\leq t}\cdots\sum\limits_{1\leq x_n\leq t}\binom{s-\sum\limits_{i=1}^n x_i}{m-n}$

如果去掉$\leq t$的限制，那么答案显然是$\binom sm$

所以对原问题考虑容斥，枚举至少有$k$个$x_i$不满足$x_i\leq t$的限制，将这些$x_i$减去$t$后就将限制变成了$1\leq x_i$，那么答案为$\sum\limits_{k=0}^n(-1)^k\binom nk\binom{s-kt}m$

接下来是构造，对于一个函数$f(x)$，对其$n$阶差分的结果为$\Delta^nf(x)=\sum\limits_{k=0}^n(-1)^{n+k}\binom nkf(x+k)$，令$f(x)=\binom{s-xt}m$，那么答案为$(-1)^n\Delta^nf(0)$

$f(x)$是一个$m$次多项式，写出它的牛顿级数$\sum\limits_{i=0}^mb_i\binom xi$并将其代入差分式中

$\begin{aligned}\Delta^nf(0)&=\sum\limits_{k=0}^n(-1)^{n+k}\binom nkf(k)\\&=\sum\limits_{k=0}^n(-1)^{n+k}\binom nk\sum\limits_{i=0}^mb_i\binom ki\\&=\sum\limits_{i=0}^mb_i\sum\limits_{k=0}^n(-1)^{n+k}\binom nk\binom ki\\&=\sum\limits_{i=0}^mb_i\binom ni(-1)^{n-i}\sum\limits_{k=0}^n(-1)^{k-i}\binom{n-i}{k-i}\\&=\sum\limits_{i=0}^mb_i\binom ni(-1)^{n-i}[n=i]\\&=b_n\end{aligned}$

所以我们只需求$b_n$，但为了求$b_n$，我们要先求$f(x)=\sum\limits_{i=0}^ma_ix^i$中的$a_i$，直接把下降幂展开成斯特林数即可，我们得到$a_i=\frac1{m!}\sum\limits_{j=i}^m(-1)^{m+i+j}\binom ji\stirf mjt^is^{j-i}$

$\begin{aligned}f(x)&=\sum\limits_{i=0}^ma_ix^i\\&=\sum\limits_{i=0}^ma_i\sum\limits_{j=0}^i\stirs ijx^{\underline j}\\&=\sum\limits_{j=0}^m\binom xj\sum\limits_{i=j}^ma_i\stirs ijj!\end{aligned}$

于是$b_n=\frac{n!(-1)^mt^n}{m!}\sum\limits_{i=0}^{m-n}\sum\limits_{j=0}^{m-n-i}(-1)^j\binom{n+i+j}j\stirs{n+i}n\stirf m{n+i+j}t^is^j$

差不多结束了，最后有一个小问题：求斯特林数

要求$\stirs nm$，虽然$n,m$都非常大，但$n-m$非常小，考虑$\stirs nm$的组合意义：将$n$个元素分为$m$个非空子集，因为最多有$n-m$个子集中的元素个数$\gt1$，设$g(n,m)$表示将$n$个元素分成$m$个子集，使得每个子集包含元素个数都$\gt1$的方案数，那么枚举$m$个子集中元素个数$\gt1$的子集个数$k$（剩下$m-k$个集合都只包含一个元素），我们得到$\stirs nm=\sum\limits_{k=0}^{n-m}\binom n{m-k}g(n-m+k,k)$

$g$的递推就和第二类斯特林数差不多了：$g(n,m)=m\cdot g(n-1,m)+(n-1)g(n-2,m-1)$

第一类也是类似的，只不过$g$的递推要相应地改成$g(n,m)=(n-1)g(n-1,m)+(n-1)g(n-2,m-1)$

于是我们可以$O\left((m-n)^2\right)$预处理并$O(m-n)$计算单个斯特林数，总的时间复杂度就是$O\left((m-n)^2\right)$了

数学真是一门化腐朽为神奇的学科==

#include
     
      typedef long long ll;const int mod=1000000007;int mul(int a,int b){return(ll)a*b%mod;}int ad(int a,int b){return(a+b)%mod;}void inc(int&a,int b){(a+=b)%=mod;}int pow(int a,int b){	int s=1;	while(b){		if(b&1)s=mul(s,a);		a=mul(a,a);		b>>=1;	}	return s;}int g1[210][210],g2[210][210],fac[210],rfac[210],inv[210];void pre(int n){	int i,j;	g1[0][0]=g2[0][0]=1;	for(i=1;i<=n;i++){		for(j=1;j*2<=i;j++){			g1[i][j]=mul(i-1,g1[i-1][j]);			g2[i][j]=mul(j,g2[i-1][j]);			if(i>1){				inc(g1[i][j],mul(i-1,g1[i-2][j-1]));				inc(g2[i][j],mul(i-1,g2[i-2][j-1]));			}		}	}	fac[0]=1;	for(i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);	rfac[n]=pow(fac[n],mod-2);	for(i=n;i>0;i--)rfac[i-1]=mul(rfac[i],i);	inv[1]=1;	for(i=2;i<=n;i++)inv[i]=-mul(mod/i,inv[mod%i]);}int binom(int n,int k){//k is small	int i,s=1;	for(i=0;i