結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:39:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,115 bytes |
コンパイル時間 | 2,432 ms |
コンパイル使用メモリ | 206,328 KB |
最終ジャッジ日時 | 2025-01-24 23:33:23 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using namespace atcoder;//using mint = modint998244353;using mint = modint1000000007;using ll = long long;using ld = long double;using pll = pair<ll, ll>;using tlll = tuple<ll, ll, ll>;constexpr ll INF = 1LL << 60;template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}ll safemod(ll A, ll M) {return (A % M + M) % M;}ll divfloor(ll A, ll B) {if (B < 0) {return divfloor(-A, -B);} return (A - safemod(A, B)) / B;}ll divceil(ll A, ll B) {if (B < 0) {return divceil(-A, -B);} return divfloor(A + B - 1, B);}#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)using mmat = vector<vector<mint>>;mmat mmatrixprod(mmat &A1, mmat &A2){ll n1 = A1.size(), n2 = A2.size();ll m1 = A1.front().size(), m2 = A2.front().size();if (n2 != m1){cerr << "Error: matrix product is not defined\n";abort();}mmat ret(n1, vector<mint>(m2, 0));for (ll i = 0; i < n1; i++){for (ll j = 0; j < m2; j++){for (ll k = 0; k < n2; k++){ret[i][j] += A1[i][k] * A2[k][j];}}}return ret;}mmat mmatrixpow(mmat &A1, ll k){ll n = A1.size();mmat A10(n, vector<mint>(n, 0));for (ll i = 0; i < n; i++){for (ll j = 0; j < n; j++){A10[i][j] = A1[i][j];}}mmat ret(n, vector<mint>(n, 0));for (ll i = 0; i < n; i++){ret[i][i] = 1;}while (k > 0){if ((k & 1) != 0)ret = mmatrixprod(ret, A10);A10 = mmatrixprod(A10, A10);k >>= 1;}return ret;}int main(){ll C, N, M;cin >> C >> N >> M;const mint inv = mint(1) / C;mmat A = {{inv, 0, 0, inv},{0, inv, (C - 1) * inv, (C - 2) * inv},{1, 0, 0, 0},{0, 1, 0, 0}};mmat pwA = mmatrixpow(A, N - 1);mmat x = {{inv}, {0}, {1}, {0}};mmat y = mmatrixprod(pwA, x);mint tmp = y.at(0).at(0);mint ans = 1 - (1 - tmp).pow(M);cout << ans.val() << endl;}