結果
問題 | No.1259 スイッチ |
ユーザー |
|
提出日時 | 2020-10-16 23:33:49 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 101 ms / 2,000 ms |
コード長 | 1,837 bytes |
コンパイル時間 | 701 ms |
コンパイル使用メモリ | 71,184 KB |
実行使用メモリ | 67,932 KB |
最終ジャッジ日時 | 2023-09-28 05:45:18 |
合計ジャッジ時間 | 8,808 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
52,804 KB |
testcase_01 | AC | 73 ms
52,580 KB |
testcase_02 | AC | 74 ms
52,632 KB |
testcase_03 | AC | 73 ms
52,776 KB |
testcase_04 | AC | 76 ms
52,544 KB |
testcase_05 | AC | 74 ms
52,648 KB |
testcase_06 | AC | 73 ms
52,812 KB |
testcase_07 | AC | 74 ms
52,580 KB |
testcase_08 | AC | 69 ms
52,612 KB |
testcase_09 | AC | 69 ms
52,580 KB |
testcase_10 | AC | 90 ms
61,476 KB |
testcase_11 | AC | 90 ms
66,812 KB |
testcase_12 | AC | 87 ms
61,108 KB |
testcase_13 | AC | 78 ms
57,636 KB |
testcase_14 | AC | 80 ms
59,728 KB |
testcase_15 | AC | 76 ms
57,324 KB |
testcase_16 | AC | 90 ms
64,372 KB |
testcase_17 | AC | 84 ms
59,472 KB |
testcase_18 | AC | 96 ms
65,820 KB |
testcase_19 | AC | 95 ms
65,796 KB |
testcase_20 | AC | 86 ms
61,736 KB |
testcase_21 | AC | 94 ms
67,044 KB |
testcase_22 | AC | 80 ms
56,664 KB |
testcase_23 | AC | 94 ms
65,484 KB |
testcase_24 | AC | 85 ms
62,328 KB |
testcase_25 | AC | 85 ms
61,992 KB |
testcase_26 | AC | 95 ms
67,252 KB |
testcase_27 | AC | 88 ms
64,556 KB |
testcase_28 | AC | 87 ms
61,980 KB |
testcase_29 | AC | 85 ms
64,564 KB |
testcase_30 | AC | 84 ms
59,860 KB |
testcase_31 | AC | 96 ms
63,448 KB |
testcase_32 | AC | 82 ms
56,768 KB |
testcase_33 | AC | 99 ms
67,508 KB |
testcase_34 | AC | 88 ms
60,476 KB |
testcase_35 | AC | 95 ms
63,936 KB |
testcase_36 | AC | 93 ms
63,200 KB |
testcase_37 | AC | 92 ms
62,272 KB |
testcase_38 | AC | 91 ms
61,436 KB |
testcase_39 | AC | 94 ms
66,920 KB |
testcase_40 | AC | 96 ms
66,880 KB |
testcase_41 | AC | 88 ms
64,216 KB |
testcase_42 | AC | 95 ms
67,124 KB |
testcase_43 | AC | 87 ms
61,000 KB |
testcase_44 | AC | 95 ms
66,624 KB |
testcase_45 | AC | 101 ms
67,840 KB |
testcase_46 | AC | 84 ms
60,660 KB |
testcase_47 | AC | 92 ms
67,532 KB |
testcase_48 | AC | 85 ms
59,632 KB |
testcase_49 | AC | 97 ms
67,052 KB |
testcase_50 | AC | 87 ms
60,908 KB |
testcase_51 | AC | 80 ms
56,856 KB |
testcase_52 | AC | 94 ms
66,944 KB |
testcase_53 | AC | 80 ms
58,740 KB |
testcase_54 | AC | 94 ms
66,720 KB |
testcase_55 | AC | 77 ms
56,660 KB |
testcase_56 | AC | 81 ms
59,488 KB |
testcase_57 | AC | 93 ms
65,612 KB |
testcase_58 | AC | 83 ms
61,432 KB |
testcase_59 | AC | 88 ms
63,492 KB |
testcase_60 | AC | 98 ms
67,932 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; const int MAX = 2100000; const int MOD = 1000000007; long long fac[MAX], finv[MAX], inv[MAX]; //invの要素にはiの逆元が格納されている //前処理 void COMinit(){ fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for(int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD;//i!(mod MOD)を計算 inv[i] = MOD - inv[MOD%i]* (MOD / i) % MOD;//iの逆元を計算 finv[i] = finv[i - 1] * inv[i] % MOD;//i!(mod MOD)の逆元を計算 } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;//nCk = n!/(k!*(n-k)!)を計算 } long long repow(long long x, long long y){ if(y == 0) return 1; long long res = 1; while(y > 0){ if(y & 1) res = res * x % MOD; x = x * x % MOD; y >>= 1; } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); COMinit(); long long N, M; long long K; cin >> N >> K >> M; long long temp = repow(N, N); long long temp2 = repow(N - 1, MOD - 2); vector<long long> ruin(N + 1); ruin[0] = 1; for(int i = 1; i < N + 1; i++){ ruin[i] = ruin[i - 1] * N % MOD; } vector<long long> kai(N + 1); kai[0] = 1; for(long long i = 1; i < N + 1; i++){ kai[i] = kai[i - 1] * i % MOD; } long long temp1 = 0; for(long long i = 1; i < N + 1; i++){ if(K % i != 0) continue; temp1 += COM(N - 1, i - 1) * ruin[N - i] % MOD * kai[i - 1] % MOD; temp1 %= MOD; } if(M == 1){ cout << temp1 << endl; } else{ long long ans = ((temp - temp1) * temp2 % MOD + MOD) % MOD; cout << ans << endl; } }