結果

問題 No.8048 Order and Harmony
コンテスト
ユーザー hitonanode
提出日時 2019-04-01 22:19:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 4,397 bytes
コンパイル時間 1,598 ms
コンパイル使用メモリ 177,964 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-27 03:11:15
合計ジャッジ時間 4,611 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#define FI first
#define SE second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))

lint K;
constexpr lint MOD = 1000000007;
// Solve ax+by=gcd(a, b)
lint extgcd(lint a, lint b, lint &x, lint &y)
{
    lint d = a;
    if (b != 0) d = extgcd(b, a % b, y, x), y -= (a / b) * x;
    else x = 1, y = 0;
    return d;
}
// Calc a^(-1) (MOD m)
lint mod_inverse(lint a, lint m)
{
    lint x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

map<lint, lint> ma;

lint get_fac(lint n)
{
    lint k = n / 10000000 * 10000000;
    lint ret = ma[k];
    FOR(j, k + 1, n + 1) ret = ret * j % MOD;
    return ret;
}
int main()
{
    ma[0] = 1;
    ma[10000000] = 682498929;
    ma[20000000] = 491101308;
    ma[30000000] = 76479948;
    ma[40000000] = 723816384;
    ma[50000000] = 67347853;
    ma[60000000] = 27368307;
    ma[70000000] = 625544428;
    ma[80000000] = 199888908;
    ma[90000000] = 888050723;
    ma[100000000] = 927880474;
    ma[110000000] = 281863274;
    ma[120000000] = 661224977;
    ma[130000000] = 623534362;
    ma[140000000] = 970055531;
    ma[150000000] = 261384175;
    ma[160000000] = 195888993;
    ma[170000000] = 66404266;
    ma[180000000] = 547665832;
    ma[190000000] = 109838563;
    ma[200000000] = 933245637;
    ma[210000000] = 724691727;
    ma[220000000] = 368925948;
    ma[230000000] = 268838846;
    ma[240000000] = 136026497;
    ma[250000000] = 112390913;
    ma[260000000] = 135498044;
    ma[270000000] = 217544623;
    ma[280000000] = 419363534;
    ma[290000000] = 500780548;
    ma[300000000] = 668123525;
    ma[310000000] = 128487469;
    ma[320000000] = 30977140;
    ma[330000000] = 522049725;
    ma[340000000] = 309058615;
    ma[350000000] = 386027524;
    ma[360000000] = 189239124;
    ma[370000000] = 148528617;
    ma[380000000] = 940567523;
    ma[390000000] = 917084264;
    ma[400000000] = 429277690;
    ma[410000000] = 996164327;
    ma[420000000] = 358655417;
    ma[430000000] = 568392357;
    ma[440000000] = 780072518;
    ma[450000000] = 462639908;
    ma[460000000] = 275105629;
    ma[470000000] = 909210595;
    ma[480000000] = 99199382;
    ma[490000000] = 703397904;
    ma[500000000] = 733333339;
    ma[510000000] = 97830135;
    ma[520000000] = 608823837;
    ma[530000000] = 256141983;
    ma[540000000] = 141827977;
    ma[550000000] = 696628828;
    ma[560000000] = 637939935;
    ma[570000000] = 811575797;
    ma[580000000] = 848924691;
    ma[590000000] = 131772368;
    ma[600000000] = 724464507;
    ma[610000000] = 272814771;
    ma[620000000] = 326159309;
    ma[630000000] = 456152084;
    ma[640000000] = 903466878;
    ma[650000000] = 92255682;
    ma[660000000] = 769795511;
    ma[670000000] = 373745190;
    ma[680000000] = 606241871;
    ma[690000000] = 825871994;
    ma[700000000] = 957939114;
    ma[710000000] = 435887178;
    ma[720000000] = 852304035;
    ma[730000000] = 663307737;
    ma[740000000] = 375297772;
    ma[750000000] = 217598709;
    ma[760000000] = 624148346;
    ma[770000000] = 671734977;
    ma[780000000] = 624500515;
    ma[790000000] = 748510389;
    ma[800000000] = 203191898;
    ma[810000000] = 423951674;
    ma[820000000] = 629786193;
    ma[830000000] = 672850561;
    ma[840000000] = 814362881;
    ma[850000000] = 823845496;
    ma[860000000] = 116667533;
    ma[870000000] = 256473217;
    ma[880000000] = 627655552;
    ma[890000000] = 245795606;
    ma[900000000] = 586445753;
    ma[910000000] = 172114298;
    ma[920000000] = 193781724;
    ma[930000000] = 778983779;
    ma[940000000] = 83868974;
    ma[950000000] = 315103615;
    ma[960000000] = 965785236;
    ma[970000000] = 492741665;
    ma[980000000] = 377329025;
    ma[990000000] = 847549272;
    ma[1000000000] = 698611116;

    cin >> K;
    if (K % 2) cout << 0 << endl;
    else
    {
        lint ans = get_fac(K);
        lint ans2 = get_fac(K / 2);
        cout << mod_inverse(ans2, MOD) * mod_inverse(ans2, MOD) % MOD * ans % MOD << endl;
    }
}
0