結果

問題 No.1327 グラフの数え上げ
コンテスト
ユーザー SnowBeenDiding
提出日時 2024-04-29 05:52:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 2,715 bytes
コンパイル時間 5,158 ms
コンパイル使用メモリ 309,824 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-18 06:45:11
合計ジャッジ時間 6,545 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace std;
using namespace atcoder;

typedef long long ll;

const long long mod = 1000000007;

struct big_stpow {
    long long mod;
    using mint = modint;

    big_stpow(long long mod = 998244353) : mod(mod) { mint::set_mod(mod); }

    vector<long long> uku = {
        1,         682498929, 491101308, 76479948,  723816384, 67347853,
        27368307,  625544428, 199888908, 888050723, 927880474, 281863274,
        661224977, 623534362, 970055531, 261384175, 195888993, 66404266,
        547665832, 109838563, 933245637, 724691727, 368925948, 268838846,
        136026497, 112390913, 135498044, 217544623, 419363534, 500780548,
        668123525, 128487469, 30977140,  522049725, 309058615, 386027524,
        189239124, 148528617, 940567523, 917084264, 429277690, 996164327,
        358655417, 568392357, 780072518, 462639908, 275105629, 909210595,
        99199382,  703397904, 733333339, 97830135,  608823837, 256141983,
        141827977, 696628828, 637939935, 811575797, 848924691, 131772368,
        724464507, 272814771, 326159309, 456152084, 903466878, 92255682,
        769795511, 373745190, 606241871, 825871994, 957939114, 435887178,
        852304035, 663307737, 375297772, 217598709, 624148346, 671734977,
        624500515, 748510389, 203191898, 423951674, 629786193, 672850561,
        814362881, 823845496, 116667533, 256473217, 627655552, 245795606,
        586445753, 172114298, 193781724, 778983779, 83868974,  315103615,
        965785236, 492741665, 377329025, 847549272, 698611116};

    long long solve(long long n) {
        if (n >= mod) return 0;
        int am = n % 10000000;
        int ka = n / 10000000 * 10000000;
        mint ret = uku[n / 10000000];
        for (int i = ka + 1; i <= ka + am; i++) ret *= i;
        return ret.val();
    }

    void uku_make(long long mod) {
        mint::set_mod(mod);
        mint now = 1;
        vector<long long> uki;
        rep(i, 1, mod) {
            if ((i - 1) % 10000000 == 0) uki.push_back(now.val());
            now *= i;
        }
        cout << '{';
        int m = uki.size();
        for (int i = 0; i < m; i++) {
            if (i % 10 == 0) cout << endl;
            if (i != m - 1)
                cout << uki[i] << ',';
            else
                cout << uki[i] << "};" << endl;
        }
    }
};

int main() {
    ll n = 0;
    rep(i, 0, 12) {
        char c;
        if (cin >> c) {
            n = n * 10 + c - '0';
        } else {
            break;
        }
    }
    modint1000000007 ans = big_stpow(mod).solve(n - 1);
    if (n % 2 == 0) ans *= -1;
    cout << ans.val() << endl;
}
0