CyclesNumber

求所有 \(n\) 个点的置换的轮换个数 \(m\) 次?的和。

\(T\leq 300,n \leq 10^5,m\leq 300\)。

题解

https://www.cnblogs.com/jefflyy/p/9425348.html

前置知识

根据《具体数学》，斯特林数有性质：

\[ \begin{Bmatrix}n+1\\m+1\end{Bmatrix}=\sum_{k=m}^n\binom{n}{k}\begin{Bmatrix}k\\m\end{Bmatrix}\\begin{bmatrix}n+1\\m+1\end{bmatrix}=\sum_{k=m}^n\binom{n}{k}\begin{bmatrix}k\\m\end{bmatrix}(n-k)!=n!\sum_{k=m}^n\frac{\begin{bmatrix}k\\m\end{bmatrix}}{k!}\\]

这两个公式的组合意义很显然，并且应该可以用归纳法证明。

还有一个类似的式子：

\[ \begin{bmatrix}n+1\\m+1\end{bmatrix}=\sum_{k=m}^n\begin{bmatrix}n\\k\end{bmatrix}\binom{k}{m} \]

但它并没有什么组合意义，尝试用归纳法证明它。

\[ \begin{bmatrix}n+1\\m+1\end{bmatrix}=\begin{bmatrix}n\\m\end{bmatrix}+n\begin{bmatrix}n\\m+1\end{bmatrix}\\begin{bmatrix}n\\m\end{bmatrix}=\sum_{k=m-1}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}\binom{k}{m-1}\n\begin{bmatrix}n\\m+1\end{bmatrix}=n\sum_{k=m}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}\binom{k}{m}\\]

注意到组合数的第二维不同，因此首要任务是把组合数拼起来。

\[ \begin{bmatrix}n\\m\end{bmatrix}=\sum_{k=m}^{n}\begin{bmatrix}n-1\\k-1\end{bmatrix}\binom{k-1}{m-1}\n\begin{bmatrix}n\\m+1\end{bmatrix}=\sum_{k=m+1}^{n}\begin{bmatrix}n-1\\k-1\end{bmatrix}\binom{k-1}{m}+(n-1)\sum_{k=m}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}\binom{k}{m}\\begin{bmatrix}n\\m\end{bmatrix}+n\begin{bmatrix}n\\m+1\end{bmatrix}=\sum_{k=m}^n\begin{bmatrix}n-1\\k-1\end{bmatrix}\left(\binom{k-1}{m-1}+\binom{k-1}{m}\right)+(n-1)\sum_{k=m}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}\binom{k}{m}\=\sum_{k=m}^n\begin{bmatrix}n-1\\k-1\end{bmatrix}\binom{k}{m}+(n-1)\sum_{k=m}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}\binom{k}{m}\=\sum_{k=m}^n\left(\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}\right)\binom{k}{m}=\sum_{k=m}^n\begin{bmatrix}n\\k\end{bmatrix}\binom{k}{m} \]

斯特林套路

这道题求的是：
\[ ans=\sum_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}i^m\=\sum_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}j!\binom{i}{j}\=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}j!\sum_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}\binom{i}{j}\=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}j!\begin{bmatrix}n+1\\j+1\end{bmatrix} \]

\(O(nm)\) 预处理第一类斯特林数，\(O(m^2)\) 预处理第二类斯特林数，就可以 \(O(m)\) 回答一个询问了

Topcoder的评测机很垃圾，感觉在给我随机打分。前后相差只有一行注释的两次提交都能得不同的分。

要想AC这题必须要把阶乘预处理到 \(n\)，我也不知道为什么。

int S1[100010][310],S2[310][310],fac[100010];

void init(int n,int m){
    S1[0][0]=1;
    for(int i=1;i<=n+1;++i)for(int j=1;j<=min(i,m+1);++j)
        S1[i][j]=add(S1[i-1][j-1],mul(i-1,S1[i-1][j]));
    S2[0][0]=1;
    for(int i=1;i<=m;++i)for(int j=1;j<=i;++j)
        S2[i][j]=add(S2[i-1][j-1],mul(j,S2[i-1][j]));
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
}
int solve(int n,int m){
    if(m==0) return fac[n];
    int ans=0;
    for(int i=0;i<=m;++i) ans=add(ans,mul(S2[m][i],mul(fac[i],S1[n+1][i+1])));
    return ans;
}

class CyclesNumber{
public:
    vector<int> getExpectation(vector<int> n,vector<int> m){
        init(1e5,300);
        vector<int> ans(n.size());
        for(int i=0;i<(int)n.size();++i) ans[i]=solve(n[i],m[i]);
        return ans;
    }
};

Topcoder CyclesNumber

原文：https://www.cnblogs.com/autoint/p/12119076.html