結果
問題 | No.1259 スイッチ |
ユーザー | milanis48663220 |
提出日時 | 2020-10-16 23:55:00 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 686 ms / 2,000 ms |
コード長 | 3,268 bytes |
コンパイル時間 | 809 ms |
コンパイル使用メモリ | 84,944 KB |
実行使用メモリ | 50,552 KB |
最終ジャッジ日時 | 2023-09-28 06:42:32 |
合計ジャッジ時間 | 21,130 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 97 ms
50,232 KB |
testcase_01 | AC | 95 ms
50,432 KB |
testcase_02 | AC | 108 ms
50,240 KB |
testcase_03 | AC | 103 ms
50,440 KB |
testcase_04 | AC | 100 ms
50,380 KB |
testcase_05 | AC | 97 ms
50,344 KB |
testcase_06 | AC | 89 ms
50,236 KB |
testcase_07 | AC | 84 ms
50,240 KB |
testcase_08 | AC | 90 ms
50,284 KB |
testcase_09 | AC | 85 ms
50,288 KB |
testcase_10 | AC | 438 ms
50,356 KB |
testcase_11 | AC | 630 ms
50,228 KB |
testcase_12 | AC | 423 ms
50,424 KB |
testcase_13 | AC | 293 ms
50,236 KB |
testcase_14 | AC | 382 ms
50,508 KB |
testcase_15 | AC | 280 ms
50,232 KB |
testcase_16 | AC | 553 ms
50,300 KB |
testcase_17 | AC | 364 ms
50,552 KB |
testcase_18 | AC | 608 ms
50,356 KB |
testcase_19 | AC | 596 ms
50,288 KB |
testcase_20 | AC | 443 ms
50,236 KB |
testcase_21 | AC | 655 ms
50,276 KB |
testcase_22 | AC | 278 ms
50,248 KB |
testcase_23 | AC | 598 ms
50,236 KB |
testcase_24 | AC | 487 ms
50,344 KB |
testcase_25 | AC | 465 ms
50,288 KB |
testcase_26 | AC | 686 ms
50,252 KB |
testcase_27 | AC | 554 ms
50,244 KB |
testcase_28 | AC | 471 ms
50,304 KB |
testcase_29 | AC | 555 ms
50,216 KB |
testcase_30 | AC | 98 ms
50,300 KB |
testcase_31 | AC | 108 ms
50,488 KB |
testcase_32 | AC | 118 ms
50,240 KB |
testcase_33 | AC | 121 ms
50,288 KB |
testcase_34 | AC | 114 ms
50,356 KB |
testcase_35 | AC | 113 ms
50,356 KB |
testcase_36 | AC | 104 ms
50,288 KB |
testcase_37 | AC | 109 ms
50,288 KB |
testcase_38 | AC | 121 ms
50,216 KB |
testcase_39 | AC | 110 ms
50,240 KB |
testcase_40 | AC | 115 ms
50,232 KB |
testcase_41 | AC | 109 ms
50,508 KB |
testcase_42 | AC | 116 ms
50,348 KB |
testcase_43 | AC | 103 ms
50,244 KB |
testcase_44 | AC | 110 ms
50,284 KB |
testcase_45 | AC | 110 ms
50,228 KB |
testcase_46 | AC | 114 ms
50,228 KB |
testcase_47 | AC | 111 ms
50,236 KB |
testcase_48 | AC | 106 ms
50,236 KB |
testcase_49 | AC | 100 ms
50,356 KB |
testcase_50 | AC | 414 ms
50,232 KB |
testcase_51 | AC | 246 ms
50,220 KB |
testcase_52 | AC | 637 ms
50,236 KB |
testcase_53 | AC | 332 ms
50,240 KB |
testcase_54 | AC | 638 ms
50,512 KB |
testcase_55 | AC | 241 ms
50,240 KB |
testcase_56 | AC | 378 ms
50,232 KB |
testcase_57 | AC | 605 ms
50,304 KB |
testcase_58 | AC | 435 ms
50,236 KB |
testcase_59 | AC | 492 ms
50,276 KB |
testcase_60 | AC | 673 ms
50,240 KB |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #define N_MAX 2000002 using namespace std; typedef long long ll; const ll MOD = 1000000007; class ModInt{ public: ll v; ModInt(ll _v = 0){ v = _v; } ModInt operator+(ll n){ return ModInt((v+n)%MOD); } ModInt operator-(ll n){ return ModInt((v-n+MOD)%MOD); } ModInt operator*(ll n){ return ModInt((v*n)%MOD); } ModInt operator/(ll n){ return ModInt((ModInt(n).inv()*v).v%MOD); } void operator+=(ll n){ v = (v+n)%MOD; } void operator-=(ll n){ v = (v-n+MOD)%MOD; } void operator*=(ll n){ v = (v*n)%MOD; } ModInt operator+(ModInt n){ return ModInt((v+n.v)%MOD); } ModInt operator-(ModInt n){ return ModInt((v-n.v+MOD)%MOD); } ModInt operator*(ModInt n){ return ModInt((v*n.v)%MOD); } ModInt operator/(ModInt n){ return ModInt((n.inv()*v).v%MOD); } void operator+=(ModInt n){ v = (v+n.v)%MOD; } void operator-=(ModInt n){ v = (v-n.v+MOD)%MOD; } void operator*=(ModInt n){ v = (v*n.v)%MOD; } void operator=(ModInt n){ v = n.v; } void operator=(ll n){ v = n; } ModInt inv(){ if(v == 1) return ModInt(1); else return ModInt(MOD-ModInt(MOD%v).inv().v*(MOD/v)%MOD); } }; ostream& operator<<(ostream& os, const ModInt& m){ os << m.v; return os; } istream & operator >> (istream &in, ModInt &m){ in >> m.v; return in; } ModInt pow(ModInt a, ll n) { ModInt ans = 1; ModInt tmp = a; for (int i = 0; i <= 60; i++) { ll m = (ll)1 << i; if (m & n) { ans *= tmp; } tmp *= tmp; } return ans; } ModInt inv[N_MAX],fac[N_MAX],finv[N_MAX]; void init(){ fac[0]=1;fac[1]=1; finv[0]=1;finv[1]=1; inv[1]=1; for(int i=2;i<N_MAX;i++){ inv[i]=(ModInt)MOD-inv[MOD%i]*(MOD/i); fac[i]=fac[i-1]*(ll) i; finv[i]=finv[i-1]*inv[i]; } } ModInt comb(ll n, ll r){ if(n < r){ return ModInt(0); }else{ return fac[n]*finv[r]*finv[n-r]; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; init(); ll n, k, m; cin >> n >> k >> m; if(m == 1 && k == 1){ cout << pow(ModInt(n), n-1) << endl; return 0; } ModInt ans = 0; // 1がloopに含まれる for(int l = 2; l <= n; l++){ if(l >= k+1 && m != 1) continue; if(k%l == 0) { if(m == 1) ans += comb(n-1, l-1)*fac[l-1]*pow(ModInt(n), n-l); }else{ if(m != 1) ans += comb(n-2, l-2)*fac[l-2]*pow(ModInt(n), n-l); } } if(m == 1){ ans += pow(ModInt(n), n-1); cout << ans << endl; return 0; } // 1がloopに含まれないかつ一周以上している for(int x = 2; x <= n; x++){ // ModInt tmp = if(k >= x) ans += comb(n-2, x-2)*fac[x-2]*pow(ModInt(n), n-x)*(x-1); else continue; } // 一周未満 if(k+1 <= n) ans += comb(n-2, k-1)*fac[k-1]*pow(ModInt(n), n-k); cout << ans << endl; }