結果

問題 No.8048 Order and Harmony
コンテスト
ユーザー AngrySadEight
提出日時 2026-02-28 23:30:35
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 5,550 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,941 ms
コンパイル使用メモリ 218,052 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-28 23:30:43
合計ジャッジ時間 7,141 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <atcoder/all>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repk(i, k, n) for (int i = k; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define mod1 1000000007
#define mod2 998244353
#define mod3 100000007
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvl vector<vector<ll>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
#define vvvl vector<vector<vector<ll>>>
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define vvpii vector<vector<pair<int, int>>>
#define vvpll vector<vector<pair<ll, ll>>>

template <typename T>
void debug(T e) {
    cerr << e << endl;
}

template <typename T>
void debug(vector<T> &v) {
    rep(i, v.size()) { cerr << v[i] << " "; }
    cerr << endl;
}

template <typename T>
void debug(vector<vector<T>> &v) {
    rep(i, v.size()) {
        rep(j, v[i].size()) { cerr << v[i][j] << " "; }
        cerr << endl;
    }
}

template <typename T>
void debug(vector<pair<T, T>> &v) {
    rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; }
}

template <typename T>
void debug(set<T> &st) {
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        cerr << *itr << " ";
    }
    cerr << endl;
}

template <typename T>
void debug(multiset<T> &ms) {
    for (auto itr = ms.begin(); itr != ms.end(); itr++) {
        cerr << *itr << " ";
    }
    cerr << endl;
}

template <typename T>
void debug(map<T, T> &mp) {
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        cerr << itr->first << " " << itr->second << endl;
    }
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << H << " ";
    debug_out(T...);
}

using mint = modint1000000007;

void debug_mint1(vector<mint> &vec) {
    for (int i = 0; i < vec.size(); i++) {
        cerr << vec[i].val() << " ";
    }
    cerr << endl;
}

void debug_mint2(vector<vector<mint>> &vec) {
    for (int i = 0; i < vec.size(); i++) {
        for (int j = 0; j < vec[i].size(); j++) {
            cerr << vec[i][j].val() << " ";
        }
        cerr << endl;
    }
}

ll batch = 5000000;

mint calc_fact(vector<mint> &embed_fact, ll v){
    ll bval = v - v % batch;
    mint ret = embed_fact[bval / batch];
    for (ll i = bval + 1; i <= v; i++){
        ret *= mint(i);
    }
    return ret;
}

int main() {
    ll K;
    cin >> K;
    if (K % 2 == 1){
        cout << 0 << endl;
        return 0;
    }
    vector<mint> fact_batch = 
    {1, 974067448, 682498929, 598816162, 491101308, 586350670, 76479948, 463847391, 723816384, 172827403, 67347853, 407719831, 27368307, 606322308, 625544428, 1669644, 199888908, 534491822, 888050723, 884343068, 927880474, 112249297, 281863274, 770511792, 661224977, 935080803, 623534362, 797848181, 970055531, 232253360, 261384175, 659224434, 195888993, 509096183, 66404266, 785113347, 547665832, 996122673, 109838563, 34538816, 933245637, 911398531, 724691727, 114985663, 368925948, 464456846, 268838846, 938269070, 136026497, 564758715, 112390913, 167240465, 135498044, 889410460, 217544623, 996097969, 419363534, 607730875, 500780548, 651081062, 668123525, 563432246, 128487469, 318951960, 30977140, 93940075, 522049725, 559947225, 309058615, 624577416, 386027524, 716986954, 189239124, 179518046, 148528617, 529726489, 940567523, 473718967, 917084264, 105419548, 429277690, 937409008, 996164327, 418537348, 358655417, 775305697, 568392357, 392838702, 780072518, 596737944, 462639908, 843321396, 275105629, 432030917, 909210595, 321685608, 99199382, 5003231, 703397904, 863250534, 733333339, 180898306, 97830135, 864869025, 608823837, 46819124, 256141983, 491415383, 141827977, 688809790, 696628828, 457469634, 637939935, 502297454, 811575797, 48053248, 848924691, 26011548, 131772368, 271198437, 724464507, 510650790, 272814771, 564188856, 326159309, 44135644, 456152084, 816929577, 903466878, 218107212, 92255682, 196345098, 769795511, 407518072, 373745190, 147050765, 606241871, 666493603, 825871994, 561011609, 957939114, 765215899, 435887178, 201339230, 852304035, 469928208, 663307737, 414236650, 375297772, 211487466, 217598709, 676526196, 624148346, 439411911, 671734977, 644050694, 624500515, 715264908, 748510389, 819801784, 203191898, 340030191, 423951674, 331910086, 629786193, 341080135, 672850561, 684748812, 814362881, 60625018, 823845496, 175638827, 116667533, 163928347, 256473217, 393556719, 627655552, 687265514, 245795606, 36292292, 586445753, 953634340, 172114298, 260466949, 193781724, 756154604, 778983779, 49031023, 83868974, 954913, 315103615, 346966053, 965785236, 321900901, 492741665, 532702135, 377329025, 847645126, 847549272, 3258987, 698611116};

    mint f = calc_fact(fact_batch, K);
    mint fhalf = calc_fact(fact_batch, K / 2);
    cout << (f / (fhalf * fhalf)).val() << endl;
}
0