(luogu6162) 四角链

发表于 分类于 ，

原题链接

思路:

令答案为 \(f(n,k)\), 则易得:

\[ f(n,k) = f(n-1,k) + (n-k)f(n-1,k-1) \]

即对 n-1 位进行讨论

可以发现这个形式很像斯特林数，令 \(g(n,k)=f(n,n-k)\), 有:

\[\begin{aligned} f(n,k) & = g(n,n-k) \\ & = g(n-1,n-k-1) + (n-k)g(n-1,n-k) \end{aligned}\]

可以看出 g 实际上就是第二类斯特林数 , 带入通项公式求解即可，即:

\[ \begin{Bmatrix}n\\ m\end{Bmatrix} = \sum_{i=0}^m \frac{(-1)^{m-i}i^n}{i!(m-i)!} \]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
using LL = long long;
const int Mn(1000500);
const LL MP(998244353);

LL ksm(LL a, LL p) {    //快速幂
    LL ret(1), tmp(a%MP);
    while(p) {
        if(p&1) {
            ret = ret*tmp%MP;
        }
        tmp = tmp*tmp%MP;
        p >>= 1;
    }
    return ret;
}
inline LL inv(LL a) {   //模乘法逆
    return ksm(a,MP-2);
}

LL fac[Mn]; //阶乘

int main() {
    int n, k;
    scanf("%d %d",&n,&k);
    fac[0] = 1;
    for(int i(1);i<=n;++i) {
        fac[i] = fac[i-1] * i % MP;
    }
    LL ans(0);
    for(int i(0);i<=n-k;++i) {  //计算
        LL tmp = (((n-k-i)&1) ? MP-1 : 1) * ksm(i,n) % MP * inv(fac[i]) % MP * inv(fac[n-k-i]) % MP;
        ans = (ans + tmp) % MP;
    }
    printf("%lld",ans);
    return 0;
}