#333035 (C++14) No.3048 Order and Harmony

提出ソース

結果

問題	No.3048 Order and Harmony
ユーザー	hitonanode
提出日時	2019-04-01 22:19:20
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	66 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	3 ms 6,816 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	2 ms 6,820 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	3 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	2 ms 6,820 KB
testcase_25	AC	66 ms 6,816 KB
testcase_26	AC	86 ms 6,816 KB
testcase_27	AC	77 ms 6,816 KB
testcase_28	AC	6 ms 6,820 KB
testcase_29	AC	2 ms 6,816 KB
testcase_30	AC	4 ms 6,816 KB
testcase_31	AC	2 ms 6,816 KB
testcase_32	AC	63 ms 6,816 KB
testcase_33	AC	2 ms 6,820 KB
testcase_34	AC	19 ms 6,816 KB
testcase_35	AC	2 ms 6,820 KB
testcase_36	AC	17 ms 6,816 KB
testcase_37	AC	90 ms 6,816 KB
testcase_38	AC	16 ms 6,820 KB
testcase_39	AC	73 ms 6,820 KB
testcase_40	AC	58 ms 6,816 KB
testcase_41	AC	76 ms 6,820 KB
testcase_42	AC	75 ms 6,816 KB
testcase_43	AC	2 ms 6,820 KB
testcase_44	AC	73 ms 6,820 KB
testcase_45	AC	18 ms 6,820 KB
testcase_46	AC	50 ms 6,816 KB
testcase_47	AC	47 ms 6,816 KB
testcase_48	AC	28 ms 6,816 KB
testcase_49	AC	2 ms 6,816 KB
testcase_50	AC	37 ms 6,820 KB
testcase_51	AC	2 ms 6,816 KB
testcase_52	AC	2 ms 6,816 KB
testcase_53	AC	93 ms 6,816 KB
testcase_54	AC	2 ms 6,816 KB
testcase_55	AC	2 ms 6,816 KB
testcase_56	AC	84 ms 6,820 KB
testcase_57	AC	2 ms 6,816 KB
testcase_58	AC	2 ms 6,816 KB
testcase_59	AC	1 ms 6,820 KB
testcase_60	AC	11 ms 6,816 KB
testcase_61	AC	61 ms 6,820 KB
testcase_62	AC	22 ms 6,816 KB
testcase_63	AC	2 ms 6,820 KB
testcase_64	AC	102 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    }
}

yukicoder

結果

テストケース

ソースコード