結果
問題 | No.1259 スイッチ |
ユーザー |
|
提出日時 | 2020-10-16 23:33:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,836 bytes |
コンパイル時間 | 696 ms |
コンパイル使用メモリ | 72,200 KB |
実行使用メモリ | 28,532 KB |
最終ジャッジ日時 | 2024-07-21 00:12:22 |
合計ジャッジ時間 | 4,782 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 RE * 45 |
ソースコード
#include <iostream>#include <vector>using namespace std;const int MAX = 410000;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;}}