結果

問題 No.2045 Two Reflections
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2022-08-20 06:15:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 2,749 bytes
コンパイル時間 1,914 ms
コンパイル使用メモリ 173,448 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-17 07:08:09
合計ジャッジ時間 2,805 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 5 ms
5,376 KB
testcase_03 AC 7 ms
5,376 KB
testcase_04 AC 7 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 7 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 AC 6 ms
5,376 KB
testcase_23 AC 6 ms
5,376 KB
testcase_24 AC 6 ms
5,376 KB
testcase_25 AC 6 ms
5,376 KB
testcase_26 AC 6 ms
5,376 KB
testcase_27 AC 5 ms
5,376 KB
testcase_28 AC 5 ms
5,376 KB
testcase_29 AC 5 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2022.08.20 06:15:16
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


class UnionFind {
private:
    vector<int> par;
public:
    UnionFind(int n) {
        par.resize(n, -1);
    }

    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return false;
        if (size(rx) < size(ry)) swap(rx, ry);
        par[rx] += par[ry];
        par[ry] = rx;
        return true;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) {
        return -par[root(x)];
    }
};

struct Osa_k {
private:
    std::vector<int> v;
public:
    Osa_k(int n) {
        assert(n >= 1);
        v.resize(n+1,-1);
        v[1] = 1;
        for(int i = 2; i <= n; i++) {
            if (v[i] != -1) continue;
            for(int j = i; j <= n; j += i) v[j] = i;
        }
    }

    std::vector<pair<int,int>> prime_factorization(int n) {
        assert(1 <= n && n < v.size());
        std::vector<int> ret;
        while(n > 1) ret.push_back(v[n]), n /= v[n];
        std::vector<pair<int,int>> ans;
        for (int i = 0; i < ret.size(); i++) {
            if (ans.size() == 0 || ans.back().first != ret[i]) {
                ans.push_back({ret[i],1});
            }
            else {
                ans.back().second++;
            }
        }
        return ans;
    }
};

constexpr int MOD = 998244353;

ll powMod(ll k, ll n, ll mod) {
    ll x = 1;
    while (n > 0) {
        if (n & 1) {
            x = x * k % mod;
        }
        k = k * k % mod;
        n >>= 1;
    }
    return x;
}

int main() {
    int n;cin >> n;
    int p,q;cin >> p >> q;
    if (p == 1 && q == 1) {
        cout << 1 << endl;
        return 0;
    }
    if (p == 1 || q == 1) {
        cout << 2 << endl;
        return 0;
    }
    if (p == n && q == n) {
        cout << 2 << endl;
        return 0;
    }
    UnionFind uf(n);
    for (int l = 0,r=p-1; l < r; l++,r--) {
        uf.unite(l,r);
    }
    for (int l = n-q,r=n-1; l < r; l++,r--) {
        uf.unite(l,r);
    }
    Osa_k osa_k(2*n);
    vector<int> v(2*n+1);
    for (int i = 0; i < n; i++) {
        if (uf.root(i) != i) continue;
        if (uf.size(i) == 1) continue;
        auto prime = osa_k.prime_factorization(2*uf.size(i));
        for (auto pp : prime) {
            v[pp.first] = max(v[pp.first],pp.second);
        }
    }
    ll ans = 1;
    for (int i = 2; i <= n; i++) {
        ans *= powMod(i,v[i],MOD);
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
0