結果
| 問題 |
No.3226 2×2行列累乗
|
| ユーザー |
 にしろ
|
| 提出日時 | 2025-08-10 20:28:50 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 10,760 bytes |
| コンパイル時間 | 6,059 ms |
| コンパイル使用メモリ | 334,468 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-08-10 20:29:00 |
| 合計ジャッジ時間 | 7,313 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ul = unsigned long;
using ld = long double;
using bl = bool;
using st = string;
using mint = atcoder::modint998244353;
using Mint = atcoder::modint1000000007;
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vvvvl vector<vvvl>
#define vd vector<ld>
#define vvd vector<vd>
#define vvvd vector<vvd>
#define vvvvd vector<vvvd>
#define vb vector<bl>
#define vvb vector<vb>
#define vvvb vector<vvb>
#define vvvvb vector<vvvb>
#define vs vector<st>
#define vvs vector<vs>
#define vvvs vector<vvs>
#define vp vector<pair<ll, ll>>
#define vvp vector<vp>
#define vvvp vector<vvp>
#define vm vector<mint>
#define vvm vector<vm>
#define vvvm vector<vvm>
#define vM vector<Mint>
#define vvM vector<vM>
#define vvvM vector<vvM>
#define cmx(n, v) n = n < v ? v : n
#define cmn(n, v) n = n > v ? v : n
#define all(n) begin(n), end(n)
#define nxp(a) next_permutation(all(a))
#define rev(n) reverse(all(n))
#define sor(n) stable_sort(all(n))
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, n) for (ll i = a; i < (n); i++)
#define rep3(i, n) for (ll i = n - 1; i >= 0; i--)
#define sz(n) n.size()
#define lb(vec, src) lower_bound(vec.begin(), vec.end(), src) - vec.begin()
#define ub(vec, src) upper_bound(vec.begin(), vec.end(), src) - vec.begin()
#define lb2(vec, src) *lower_bound(vec.begin(), vec.end(), src)
#define ub2(vec, src) *upper_bound(vec.begin(), vec.end(), src)
#define mn1(a) min_element(all(a))
#define mx1(a) max_element(all(a))
#define mn2(a) *min_element(all(a))
#define mx2(a) *max_element(all(a))
#define uniq(a) \
{ \
sort(all(a)); \
(a).erase(unique(all(a)), (a).end()); \
}
#define DET2(x1, y1, x2, y2) (x1) * (y2) - (x2) * (y1)
#define DET3(x1, y1, z1, x2, y2, z2, x3, y3, z3) \
(x1) * (y2) * (z3) + (x2) * (y3) * (z1) + (x3) * (y1) * (z2) - \
(z1) * (y2) * (x3) - (z2) * (y3) * (x1) - (z3) * (y1) * (x2)
const ll inf = 9e18;
ll calc_digit(ll N) {
ll res = 0;
while (N > 0) {
res++;
N /= 10;
}
return res;
}
ll factorial(ll n, ll mod = 1e18) {
ll ans = 1;
for (ll i = n; i >= 2; i--)
ans = (ans * i) % mod;
return ans;
}
ll floor_int(ll x, ll m) {
ll r = (x % m + m) % m; // 負の剰余を正の剰余に置き換える
return (x - r) / m; // return
}
ll round_up(ll x, ll y) {
ll res = (x + y - 1) / y;
return res;
}
ll rmd(ll x, ll m) {
ll r = (x % m + m) % m; // 負の剰余を正の剰余に置き換える
return r;
}
ll rmd_2(ll x, ll m) {
ll r = (x % m + m) % m; // 負の剰余を正の剰余に置き換える
return (m - r) % m; // return
}
ll bubble_sort(vl a, ll n) {
ll res = 0;
rep(i, n - 1) {
for (ll j = n - 1; j > i; j--) {
if (a[j - 1] > a[j]) {
swap(a[j - 1], a[j]);
res++;
}
}
}
return res;
}
ll sum_v(vl a) {
ll res = 0;
ll n = sz(a);
rep(i, n) res += a[i];
return res;
}
ll stair_sum(ll from, ll to) { return (from + to) * (to - from + 1) / 2; }
ll Power(ll var, ll p) {
if (p == 1)
return var;
ll ans = Power(var * var, p / 2);
if (p & 1)
ans *= var;
return ans;
}
ll cnt_01(ll n, ll now) {
ll res = 0;
res += (n / now) * (now / 2);
if (n % now >= now / 2)
res += n % now - (now / 2) + 1;
return res;
}
ll sum_pop(ll n) {
ll res = 0;
for (ll b = 0; b < 60; b++) {
res += (n / (1ll << (b + 1))) * (1ll << b);
res += max(0ll, n % (1ll << (b + 1)) - (1ll << b) + 1);
}
return res;
}
ll Tree_Diameter(vvl &g) {
ll n = sz(g);
ll start = 0;
ll ans = 0;
for (ll i = 0; i < 2; i++) {
queue<ll> q;
q.push(start);
vl dis(n, inf);
dis[start] = 0;
while (!q.empty()) {
ll u = q.front();
q.pop();
start = u;
ans = dis[u];
for (ll v : g[u]) {
if (dis[v] != inf)
continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return ans;
}
ll calc_sum_of_abs_dis(vl a) {
sor(a);
ll n = sz(a);
ll res = 0;
rep(i, n) res += a[i] * (2 * i + 1 - n);
return res;
}
bool is_prime(ll N) {
if (N == 1)
return false;
if (N == 2)
return true;
if (N % 2 == 0)
return false;
for (ll p = 3; p * p <= N; p += 2)
if (N % p == 0)
return false;
return true;
}
bool in_out(ll x, ll y, ll h, ll w) {
return 0 <= x and x < h and 0 <= y and y < w;
}
bool dis_solve1(ll x1, ll x2, ll y1, ll y2, ll r) {
ll xx = (x1 - x2), yy = (y1 - y2);
ll dis = xx * xx + yy * yy;
return (r * r == dis);
}
bool dis_solve2(ll x1, ll x2, ll y1, ll y2, ll d1, ll d2) {
ll xx = (x1 - x2), yy = (y1 - y2), r1 = (d1 + d2), r2 = (d1 - d2);
ll dis = xx * xx + yy * yy;
return (r2 * r2 <= dis && dis <= r1 * r1);
}
void printl(vl v, ll len = 0) {
ll vsz = min(len, ll(v.size()));
for (ll i = 0; i < vsz; i++) {
cout << v[i] << endl;
}
}
void prints(vs v) {
ll vsz = v.size();
for (ll i = 0; i < vsz; i++) {
cout << v[i] << endl;
}
}
vl p_list(ll n) {
vl res;
vb check(n + 1);
for (ll i = 2; i <= n; i++) {
if (check[i])
continue;
res.push_back(i);
ll ii = i;
while (ii <= n) {
check[ii] = true;
ii += i;
}
}
return res;
}
vl cumulative_sum(vl a) {
ll s = sz(a);
vl b(s + 1, 0);
for (ll i = 0; i < s; i++) {
b[i + 1] = a[i] + b[i];
}
return b;
}
vl n_num(ll a, ll n) {
vl res;
while (a) {
res.push_back(a % n);
a /= n;
}
rev(res);
return res;
}
vl c_press(vl a) {
ll n = sz(a);
vl res = a, c = a;
sor(c);
uniq(c);
rep(i, n) res[i] = lb(c, res[i]);
return res;
}
vl min_fact(ll n) {
vl pl;
vl res(n + 1, -1);
for (ll d = 2; d <= n; d++) {
if (res[d] == -1) {
res[d] = d;
pl.push_back(d);
}
for (ll p : pl) {
if (p * d > n || p > res[d])
break;
res[p * d] = p;
}
}
return res;
}
vvl to_grid(vl &a, ll k) {
ll n = sz(a);
ll m = (n + k - 1) / k;
vvl b(k, vl(m, inf));
rep(i, n) b[i % k][i / k] = a[i];
return b;
}
vvl rotate_ll(vvl &V2d, ll wise) {
vvl a = V2d;
ll h = sz(a), w = sz(a[0]);
vvl res(w, vl(h));
if (wise) {
rep(i, h) rep(j, w) res[j][h - i - 1] = a[i][j];
} else {
rep(i, h) rep(j, w) res[w - j - 1][i] = a[i][j];
}
return res;
}
vs rotate_st(vs s, ll wise) {
vs a = s;
ll h = sz(a), w = sz(a[0]);
vs res(w);
rep(i, w) res[i].append(h, '.');
if (wise) {
rep(i, h) rep(j, w) res[j][h - i - 1] = a[i][j];
} else {
rep(i, h) rep(j, w) res[w - j - 1][i] = a[i][j];
}
return res;
}
vp prime_factorize(ll N) {
vp res;
for (ll a = 2; a * a <= N; ++a) {
if (N % a != 0)
continue;
ll ex = 0;
while (N % a == 0) {
ex++;
N /= a;
}
res.push_back({a, ex});
}
if (N != 1)
res.push_back({N, 1});
return res;
}
vector<pair<ll, ll>> RLEint(vl a) {
ll n = sz(a);
vector<pair<ll, ll>> res;
res.push_back({a[0], 1});
for (ll i = 1; i < n; i++) {
if (res.back().first != a[i]) {
res.push_back({a[i], 1});
} else {
res.back().second++;
}
}
return res;
}
vector<pair<char, ll>> RLEchar(st s) {
ll n = sz(s);
vector<pair<char, ll>> res;
res.push_back({s[0], 1});
for (ll i = 1; i < n; i++) {
if (res.back().first != s[i]) {
res.push_back({s[i], 1});
} else {
res.back().second++;
}
}
return res;
}
template <typename T> void input(T &a) { cin >> a; };
template <typename T1, typename... T2> void input(T1 &a, T2 &...b) {
cin >> a;
input(b...);
};
template <typename T = ll> vector<T> rd(size_t n) {
vector<T> ts(n);
for (size_t i = 0; i < n; i++)
cin >> ts[i];
return ts;
}
ll di[8] = {1, -1, 0, 0, 1, 1, -1, -1};
ll dj[8] = {0, 0, 1, -1, 1, -1, -1, 1};
// abcdefghijklmnopqrstuvwxyz
// std::setprecision(15);
// 2^29<10^9
//|\__/|
//(☆θωθ)☆ :mimamoriEtoigne:
//_(:3」∠)_ :mimamoriJunsuke:
struct doubling {
vector<vector<ll>> d;
ll n;
doubling(vector<ll> a) {
n = a.size();
d.resize(60);
for (ll i = 0; i < 60; i++)
d[i].resize(n);
d[0] = a;
}
void calc() {
for (ll i = 0; i < 59; i++) {
for (ll j = 0; j < n; j++) {
d[i + 1][j] = d[i][d[i][j]];
}
}
}
vector<ll> get_ans(ll k) {
vector<ll> res(n);
for (ll i = 0; i < n; i++) {
res[i] = i;
}
for (ll j = 0; j < 60; j++) {
for (ll i = 0; i < n; i++) {
if (!(k >> j & 1))
continue;
res[j] = d[i][res[j]];
}
}
return res;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vvvl dp(65, vvl(2, vl(2)));
ll s, t, n, k;
cin >> dp[0][0][0] >> dp[0][0][1] >> dp[0][1][0] >> dp[0][1][1];
cin >> s >> t >> n >> k;
dp[0][0][0] = rmd(dp[0][0][0], k);
dp[0][0][1] = rmd(dp[0][0][1], k);
dp[0][1][0] = rmd(dp[0][1][0], k);
dp[0][1][1] = rmd(dp[0][1][1], k);
s = rmd(s, k);
t = rmd(t, k);
rep(x, 60) {
rep(i, 2) rep(j, 2) {
rep(d, 2) {
dp[x + 1][i][j] += dp[x][i][d] * dp[x][d][j];
dp[x + 1][i][j] %= k;
}
}
}
vvl res = {{1, 0}, {0, 1}};
rep(x, 60) {
if (n >> x & 1) {
vvl nres = {{0, 0}, {0, 0}};
rep(i, 2) rep(j, 2) {
rep(d, 2) {
nres[i][j] += dp[x][i][d] * res[d][j];
nres[i][j] %= k;
}
}
swap(res, nres);
}
}
vl ans(2);
rep(i, 2) {
ans[i] += s * res[i][0];
ans[i] += t * res[i][1];
ans[i] %= k;
}
cout << ans[0] << " " << ans[1];
}