博客使用更佳：

https://www.cnblogs.com/czyty114/p/14742702.html
考试的时候已经尽我可能想到一半了，没想到最后我推的柿子竟然就是第一类斯特林数

题意

$\;$
初始时有一个$1$到$n$的排列，一次操作可以交换两个数的位置。
现在，对于所有的$i\;(1\leq i\leq k)$，求你恰好进行了$i$次操作，能得到的不同排列有多少种
$n\leq 10^9, k\leq 200$
$\;$
input
3 2
output
3 3
$\;$

$\;$

Solution

$\;$
不妨去想，如果初始的排列$1,2,\cdots,n$，其最少能通过$x$次变成一个排列$A$
那么一定也可以通过$x+2,x+4,\cdots$次操作变成$A$
反过来，通过$x+1,x+3,\cdots$这样次数的操作一定不可以变成$A$

如何求$x$?
我们倒过来想，把$A$变成$1,2,\cdots,n$
首先一个排列一定可以被划分成若干个圆（我习惯称其为轨道）
轨道是什么？
对于这个排列$2 \;5 \;4 \;3 \;1$，2占了1的位置，1占了5的位置，5占了2的位置，那么就构成了一个轨道$\{2,1,5\}$
同理，还有$\{4,3\}$这个轨道。
显然，每次操作，我们交换轨道的内的数是更优的。
而对于每个轨道，假如其长度为$r$，我们最少需要$r-1$次操作，把这个轨道内的数都恢复到原位。
所以假如说一个排列有$c$个轨道，我们最少只用进行$n-c$次操作，就可以把所有数回归原位
$\;$
考试的时候想到这里不会了。
考完，上网一查。
！第一类斯特林数（当场自闭
$\;$

第一类斯特林数

$\;$
$S1(n,m)$代表一个长度为$n$的排列被划分成$m$个轨道的方案数
显然
$S1(n,m)=S1(n-1,m-1)+(n-1)S1(n-1,m)$
但如果只是这样递推是$O(n^2)$的
而$n\leq 10^9$
$\;$

处理n很大的情况

$\;$
第一类斯特林数还有一个比较好的柿子：
$$S1(n,m)=(-1)^{n-m}\sum_{i=0}^{n-m} (-1)^i \times C(n-1+i,n-m+i) \times C(2n-m,n-m-i) \times S(n-m+i,i)$$
$\;$
但这玩意我不会证明，目前先知道就行
而我们现在要求的是$S1(n,n-i) (0\leq i\leq k)$
所以预处理出组合数和第二类斯特林数$O(k^3)$求解
$\;$

Code

#include <bits/stdc++.h>

const int N = 410, mod = 1000000007;

int n, k, fac[N], inv[N], S[N][N], dp[N];

int C(int n, int m) {
    int ans = 1;
    for (int i = n; i >= n - m + 1; i --) ans = 1ll * ans * i % mod;
    return 1ll * ans * inv[m] % mod;
}

int power(int a, int b) {
    int ans = 1;
    while(b) {
        if (b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1; 
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &k);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= 400; i ++) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = power(fac[i], mod - 2);
    }
    S[0][0] = 1;
    for (int i = 1; i <= 400; i ++) 
        for (int j = 1; j <= i; j ++)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j] % mod) % mod;
    for (int i = 0; i <= k; i ++) // 求s(n,n-i)
        for (int j = 0; j <= i; j ++) {
            if (j & 1)
                dp[i] = (dp[i] - 1ll * C(n - 1 + j, i + j) * C(n + i, i - j) % mod * S[i + j][j] % mod + mod) % mod;
            else
                dp[i] = (dp[i] + 1ll * C(n - 1 + j, i + j) * C(n + i, i - j) % mod * S[i + j][j] % mod) % mod;
        } 
    for (int i = 1; i <= k; i ++) {
        int ans = 0;
        for (int j = 0; j <= i; j += 2)
            ans = (ans + dp[i - j]) % mod;
        if (i % 2 == 0) printf("%d ", ans);
        else printf("%d ", mod - ans);
    }
    return 0;
}