順列 (nPr) (test/EnumerativeCombinatorics/combination_prime_mod/local/perm.cpp)

View this file on GitHub
View document part on GitHub
Last update: 2026-05-17 15:50:36+09:00

順列 (nPr)

問題文

$Q$ 個のクエリが与えられます。

各クエリでは、整数 $n, r$ が与えられるので、順列 $nPr$ を $998244353$ で割った余りを求めてください。

順列 $nPr$ は、$n$ 個の異なるものから $r$ 個を選んで並べる場合の数であり、次の式で表されます。

\[nPr = \frac{n!}{(n-r)!}\]

ただし、$r > n$ の場合は $0$ とします。

入力

Q
n_1 r_1
n_2 r_2
...
n_Q r_Q

出力

$Q$ 行出力してください。

$i$ 行目には、$n_iPr_i$ を $998244353$ で割った余りを出力してください。

制約

$1 \leq Q \leq 200000$
$0 \leq n_i \leq 200000$
$0 \leq r_i \leq 200000$
入力はすべて整数

Depends on

組合せ・順列・重複組合せ (素数 mod) (EnumerativeCombinatorics/combination_prime_mod.hpp)

Code

// competitive-verifier: LOCALCASE ./cases/perm

#include "EnumerativeCombinatorics/combination_prime_mod.hpp"
#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int Q;
    cin >> Q;

    combinatorics<atcoder::modint998244353> comb(1e6);

    for (int q = 0; q < Q; q++)
    {
        int n, r;
        cin >> n >> r;
        cout << comb.P(n, r).val() << endl;
    }

    return 0;
}

#line 1 "test/EnumerativeCombinatorics/combination_prime_mod/local/perm.cpp"
// competitive-verifier: LOCALCASE ./cases/perm

#line 1 "EnumerativeCombinatorics/combination_prime_mod.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class mint>
class combinatorics
{
private:
    int max_n;
    vector<mint> fact, ifact;

public:
    combinatorics(int n) : max_n(n), fact(n + 1), ifact(n + 1)
    {
        assert(n < mint::mod());

        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;

        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k)
    {
        return C(n, k);
    }

    // nCr
    mint C(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[r] * ifact[n - r];
    }

    // nPr
    mint P(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[n - r];
    }

    // nHr
    mint H(int n, int r)
    {
        if (n < 0 || r < 0)
            return 0;

        if (n == 0)
            return r == 0 ? 1 : 0;

        return C(n + r - 1, r);
    }
};
#line 4 "test/EnumerativeCombinatorics/combination_prime_mod/local/perm.cpp"
#include <atcoder/modint>
#line 6 "test/EnumerativeCombinatorics/combination_prime_mod/local/perm.cpp"

using namespace std;

int main()
{
    int Q;
    cin >> Q;

    combinatorics<atcoder::modint998244353> comb(1e6);

    for (int q = 0; q < Q; q++)
    {
        int n, r;
        cin >> n >> r;
        cout << comb.P(n, r).val() << endl;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_fixed_1	AC	14 ms	11 MB
g++	02_random_1	AC	29 ms	11 MB
g++	02_random_2	AC	40 ms	11 MB
g++	02_random_3	AC	34 ms	11 MB
g++	02_random_4	AC	37 ms	11 MB
g++	02_random_5	AC	35 ms	11 MB