(luogu6162)四角链

发表于 | 分类于 ，

原题链接

思路:

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

即对n-1位进行讨论

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

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

代码:

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;
}