$\quad $ 其中 $n\le 1e3 $ 、$ m\le 1e9 $ 、 $ T\le 10 $。
$\quad $ 这是一个排列问题，所以我们可以考虑指数型生成函数，这里我们称 \(x ^n\) 的系数为 \(\frac{x ^n}{n!}\) 之前的系数，下文记作 \([x ^n]\) 。
$\quad $ 我们定义函数 \(f _{k}(x)=\sum _{n=0}^{k}\frac{x ^n}{n!}\) ，那么 \([x^n]\) 表示选其中 \(n\) 个数（可重）且该数出现次数不超过 \(k\) 时的合法方案数。
$\quad $ 那么 \([x^n]e _{k}^{m}(x)\) 就表示在 \(m\) 个数中选出 \(n\) 个数（可重），使得每个选出的数出现次数都不超过 \(k\) 的方案数。
$\quad $ 那么 \([x^n]e_{k}^{m}(x)-[x^n]e _{k-1}^{m}(x)\) 就表示在 \(m\) 个数中选出 \(n\) 个数（可重），使得众数为 \(k\) 的方案数。
下文的 \([x^n]\) 代指 \(x^n\) 之前的系数。
$\quad $ 答案就是：
\[n!\sum _{k=1}^{n}k([x^n]e ^{m}_{k}(x)-[x^n]e ^{m}_{k-1}(x)) \]再化简一下：
\[n!(n[x^n]e ^{m}_{n}(x)-\sum _{k=1}^{n-1}[x^n]e ^{m} _{k}(x)) \]$\quad $ 现在再考虑求出 \([x^n]e _{k}^{m}(x)\)
首先对 \(e ^m_{k}(x)\) 求导，这里用到了复合函数的求导，（简单写了，不是很严谨）即：
对于两个函数 \(f(x)、g(x)\) ，令 \(h(x)=f[g(x)]\) ，则 \(h'(x)=f'[g(x)] g'(x)\)
书上给的
如果 \(u=g(x)\) 在点 \(x\) 处可导，而 \(y=f(u)\) 在点 \(u=g(x)\) 处可导，那么复合函数 \(y=g[f(x)]\) 在点 \(x\) 处可导，且其导数为
\[\frac{dy}{dx}=f'(u)\cdot g'(x) \]这里我们可以把 \(e ^m_{k}(x)\) 看做是 $f(x)=x^m $ 和 \(g(x)=e _{k}(x)\) 的复合函数
那么：
\[(e ^{m}_{k}(x))'=me ^{m-1}_{k}(x)e'_{k}(x) \]现在看看 \(e'_{k}(x)\) ，因为 \(e _{k}(x)=\sum _{i=0}^{k}\frac{x^i}{i!}\) ，故 \(e'_{k}(x)=\sum _{i=1}^{k}\frac{x ^{i-1}}{(i-1)!}=\sum _{i=0}^{k-1}\frac{x^i}{i!}=e _{k}(x)-\frac{x^k}{k!}\) 。
所以：
\begin{aligned}
(e ^{m}_{k}(x))'&=me ^{m-1} _{k}(x) e' _{k} (x)\\
&=me ^{m-1} _{k}(x)(e _{k} ^{m}(x)-\frac{x ^k}{k!})\\
&=m e ^{m} _{k}(x)-\frac{mx ^k}{k!}e _{k} ^{m-1}(x)\\
\end{aligned}
那么对于其 \(n\) 次项系数，该等式仍然成立。
也就是：
\[[x^n](e ^{m}_{k}(x))'=[x^n]m e ^{m} _{k}(x)-\frac{mx ^k}{k!}[x ^{n-k}]e _{k} ^{m-1}(x) \]此时设 \(e _{k} ^{m}(x)=\sum _{n=0}^{m}A(n,m)x^n\) ，那么可知 \([x^n](e ^{m}_{k}(x))' =(n+1)A(n+1,m)\)
于是：
\[(n+1)A(n+1,m)=mA(n,m)-\frac{m}{k!}A(n-k,m-1) \]$\quad $ 再化成我们熟悉的递推式：
\[iA(i,j)=jA(i-1,j)-\frac{j}{k!}A(i-k-1,j-1) \]$\quad $ 当 \(m=1\) 时，该式的值为 \(\frac{1}{n!}\) ， \(n=0\) 时，该式的值为 \(1\) ， \(n\le 0\) 时则为 \(0\) 。
然后愉快递推就好了，时间复杂度 \(O(n ^2 log n)\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int N=1e3+10,p=1e9+7;
int fact[N],n,m,t,ny[N],nyp[N],k,f[N][N];
inline int qum(int a,int b){
int ans=1;
while(b){
(b&1)&&(ans=ans*a%p);
a=a*a%p;
b>>=1;
}
return ans;
}
signed main(){
// freopen("1.in","r",stdin);
freopen("capital.in","r",stdin);
freopen("capital.out","w",stdout);
scanf("%lld",&t);fact[0]=1;
for(int i=1;i<=1000;i=-~i)fact[i]=fact[i-1]*i%p;
ny[1000]=qum(fact[1000],p-2);
for(int i=999;i;i--)ny[i]=ny[i+1]*(i+1)%p;
for(int i=1;i<=1000;i=-~i)nyp[i]=fact[i-1]*ny[i]%p;
while(t--){
scanf("%lld%lld",&n,&m);
int ans=0;
for(int i=1;i<=n+1;i++)f[0][i]=1;
for(k=1;k<=n;k=-~k){
f[k][1]=ny[k];
int op=n/k+1,d=m-op;
for(int i=1;i<=op;i=-~i){
for(int j=1;j<=k;j=-~j){
f[j][i]=nyp[j]*(i+d)%p*f[j-1][i]%p;
}
for(int j=k+1;j<=n;j++){
f[j][i]=nyp[j]*(i+d)%p*(f[j-1][i]-ny[k]*f[j-k-1][i-1]%p+p)%p;
}
}
ans=(k^n)?(ans+f[n][m-d])%p:(n*f[n][m-d]%p-ans+p)%p;
}
ans=ans*fact[n]%p;
printf("%lld\n",ans);
}
}
《唐完了》，5k一语惊醒梦中人。
