test/library_checker/enumerative_combinatorics/many_factorials.test.cpp

• View this file on GitHub
• Last update: 2024-11-25 17:28:12+09:00
• Problem: https://judge.yosupo.jp/problem/many_factorials

Depends on

• Factorial (階乗) (lib/enumerative_combinatorics/factorial.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/many_factorials"
#include <iostream>

#include "../../../lib/enumerative_combinatorics/factorial.hpp"

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ManyFactorials<long long> fact(998244353LL);
    int t;
    cin >> t;
    while(t--){
        int n; cin >> n;
        cout << fact.factorial(n) << "\n";
    }
}

#line 1 "test/library_checker/enumerative_combinatorics/many_factorials.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/many_factorials"
#include <iostream>

#line 2 "lib/enumerative_combinatorics/factorial.hpp"

/**
 * @brief Factorial (階乗)
 */

#include <vector>
#include <cmath>

long long factorial_998244353(int n){
    const int BLOCK = 10000000;
    constexpr long long memo[] = {1, 295201906, 160030060, 957629942, 545208507, 213689172, 760025067, 939830261, 506268060, 39806322, 808258749, 440133909, 686156489, 741797144, 390377694, 12629586, 544711799, 104121967, 495867250, 421290700, 117153405, 57084755, 202713771, 675932866, 79781699, 956276337, 652678397, 35212756, 655645460, 468129309, 761699708, 533047427, 287671032, 206068022, 50865043, 144980423, 111276893, 259415897, 444094191, 593907889, 573994984, 892454686, 566073550, 128761001, 888483202, 251718753, 548033568, 428105027, 742756734, 546182474, 62402409, 102052166, 826426395, 159186619, 926316039, 176055335, 51568171, 414163604, 604947226, 681666415, 511621808, 924112080, 265769800, 955559118, 763148293, 472709375, 19536133, 860830935, 290471030, 851685235, 242726978, 169855231, 612759169, 599797734, 961628039, 953297493, 62806842, 37844313, 909741023, 689361523, 887890124, 380694152, 669317759, 367270918, 806951470, 843736533, 377403437, 945260111, 786127243, 80918046, 875880304, 364983542, 623250998, 598764068, 804930040, 24257676, 214821357, 791011898, 954947696, 183092975};
    if(n >= 998244353){
        return 0;
    }
    int d = n / BLOCK;
    long long res = memo[d];
    for(int i = d * BLOCK + 1; i <= n; ++i){
        res = res * i % 998244353;
    }
    return res;
}

template <typename T>
struct ManyFactorials{
    const T BLOCK, MOD;
    std::vector<T> memo;
    ManyFactorials(const T MOD) : BLOCK((T) ((sqrtl(MOD) + 49) / 50)), MOD(MOD){
        setup();
    }

    void setup(){
        memo = {1};
        T cur = 1;
        for(T i = 1; i < MOD; ++i){
            cur = cur * i % MOD;
            if(i % BLOCK == 0){
                memo.push_back(cur);
            }
        }
    }

    T factorial(T n){
        if(n >= MOD){
            return 0;
        }
        T d = n / BLOCK;
        T res = memo[d];
        for(T i = d * BLOCK + 1; i <= n; ++i){
            res = res * i % MOD;
        }
        return res;
    }
};
#line 5 "test/library_checker/enumerative_combinatorics/many_factorials.test.cpp"

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ManyFactorials<long long> fact(998244353LL);
    int t;
    cin >> t;
    while(t--){
        int n; cin >> n;
        cout << fact.factorial(n) << "\n";
    }
}

Back to top page