0%

Codeforces 1342E - Placing Rooks

发表于

原文

Calculate the number of ways to place nn rooks on n×nn\times n chessboard so that both following conditions are met:

  • each empty cell is under attack;
  • exactly kk pairs of rooks attack each other.

An empty cell is under attack if there is at least one rook in the same row or at least one rook in the same column. Two rooks attack each other if they share the same row or column, and there are no other rooks between them. For example, there are only two pairs of rooks that attack each other in the following picture:

One of the ways to place the rooks for n=3n=3 and k=2k=2

Two ways to place the rooks are considered different if there exists at least one cell which is empty in one of the ways but contains a rook in another way.

The answer might be large, so print it modulo 998244353.

Input

The only line of the input contains two integers nn and kk (1≤n≤2000001\le n\le 200000; 0≤k≤n(n−1)20\le k\le\frac{n(n-1)}{2}).

Output

Print one integer — the number of ways to place the rooks, taken modulo 998244353.

Examples

input

1
3 2

output

1
6

input

1
3 3

output

1
0

input

1
4 0

output

1
24

input

1
1337 42

output

1
807905441

题意

rook可以对同一行和同一列攻击，提供两个数nn和kk，求在n×nn\times n的棋盘上放置nn个rook使得：

  • 所有棋盘格都可以被攻击到
  • 有kk对rook可以互相供给

的放置方法总数。

思路

由于所有地方都需要被攻击到，那么就相当于一定是每个行都有一个rook或者每个列都有一个rook.本质上是一个排列组合问题，可以发现，行和列实际上是对称的，所以只需要考虑行列当中的一种。

假设每个行上都有一个rook，如果k≠0k\ne0，那么必然是nn个rook分布在n−kn-k个列上。对应的排列方法一共有：

(n−k)n−Cn−kn−k−1(n−k−1)n+Cn−kn−k−2(n−k−2)n=∑i=0n−k(−1)iCn−ki(n−k−i)n(n-k)^n - C_{n-k}^{n-k-1}(n-k-1)^n+C_{n-k}^{n-k-2}(n-k-2)^n=\sum_{i=0}^{n-k}(-1)^i C_{n-k}^{i}(n-k-i)^n

从上面的分析也可以发现，如果k≥nk\ge n，那么不存在符合的情况。再注意当k≠0k\ne0的时候需要，需要乘2，而k=0k=0的时候直接作为结果就可以了。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MOD 998244353

#define add(x,y) ((x+y)%MOD)
#define mul(x,y) ((x*y)%MOD)
#define sub(x,y) ((MOD+x-y)%MOD)

ll fastpow(ll x, ll y){
    ll temp = 1;
    while(y){
        if(y&1)
            temp = mul(temp, x);
        x = mul(x, x);
        y>>=1;
    }
    return temp;
}

ll inv(ll x){
    return fastpow(x,MOD-2);
}

ll frac[200100];

ll C(ll n, ll i){
    return mul(frac[n], inv(mul(frac[i], frac[n-i])));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,k;
    cin>>n>>k;
    
    if(k>=n){
        cout<<0<<endl;
        return 0;
    }

    ll ans = 0;
    frac[0] = 1;
    for(int i=1;i<=n;++i){
        frac[i] = mul(i, frac[i-1]);
    }
    for(int i=0;i<=n-k;++i){
        ll temp = mul(C(n-k,i), fastpow(n-k-i,n));
        if(i&1)
            ans = sub(ans, temp);
        else
            ans = add(ans,temp);
    }

    ans = mul(ans, C(n, n-k));
    if(k)
        ans = mul(ans, 2);
    cout<<ans<<endl;
}