結果
問題 | No.840 ほむほむほむら |
ユーザー | kotamanegi |
提出日時 | 2019-06-14 22:55:18 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 411 ms / 4,000 ms |
コード長 | 2,776 bytes |
コンパイル時間 | 1,465 ms |
コンパイル使用メモリ | 108,784 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-08-09 06:29:27 |
合計ジャッジ時間 | 6,255 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 9 ms
4,380 KB |
testcase_03 | AC | 52 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,384 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,384 KB |
testcase_07 | AC | 16 ms
4,384 KB |
testcase_08 | AC | 94 ms
4,384 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 3 ms
4,380 KB |
testcase_12 | AC | 26 ms
4,380 KB |
testcase_13 | AC | 224 ms
4,380 KB |
testcase_14 | AC | 28 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,384 KB |
testcase_16 | AC | 4 ms
4,384 KB |
testcase_17 | AC | 53 ms
4,380 KB |
testcase_18 | AC | 294 ms
4,384 KB |
testcase_19 | AC | 372 ms
4,384 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,380 KB |
testcase_22 | AC | 5 ms
4,380 KB |
testcase_23 | AC | 411 ms
4,380 KB |
testcase_24 | AC | 5 ms
4,384 KB |
testcase_25 | AC | 1 ms
4,384 KB |
testcase_26 | AC | 7 ms
4,380 KB |
testcase_27 | AC | 353 ms
4,384 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include <random> #include<map> #include <iomanip> #include <time.h> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> #include <cassert> #include<fstream> #include <unordered_map> #include <cstdlib> #include <complex> using namespace std; #define Ma_PI 3.141592653589793 #define eps 0.00000001 #define LONG_INF 30000000000000LL #define GOLD 1.61803398874989484820458 #define MAX_MOD 998244353LL #define REP(i,n) for(long long i = 0;i < n;++i) #define seg_size 524288 long long powering(long long now,long long now_go){ long long ans = 1; while (now_go != 0) { if (now_go % 2 == 1) { ans *= now; ans %= MAX_MOD; } now *= now; now %= MAX_MOD; now_go /= 2; } return ans; } vector<long long> calc(vector<long long> a, vector<long long> b) { long long k = sqrt(a.size()); vector<long long> ans; for (int i = 0; i < k; ++i) { for (int q = 0; q < k; ++q) { //ans[i][q]を計算する long long geko = 0; for (int t = 0; t < k; ++t) { geko += a[i * k + t] * b[t * k + q]; geko %= MAX_MOD; } ans.push_back(geko); } } return ans; } vector<long long> powered(vector<long long> a, long long n) { vector<long long> ans = a; n--; while (n != 0) { if (n % 2 == 1) { ans = calc(ans, a); } a = calc(a, a); n /= 2; } return ans; } long long inv(long long now) { return powering(now, MAX_MOD - 2LL); } int main(){ long long n, k; cin >> n >> k; //行列構築 vector<long long> starter; REP(i, k*k*k) { int now = i; int a = now % k; now /= k; int b = now % k; now /= k; int c = now % k; REP(j, k*k*k) { now = j; int d = now % k; now /= k; int e = now % k; now /= k; int f = now % k; //take A int ok = 0; if ((a + 1) % k == d&&b == e&&c == f) { ok++; } //take B if (a == d && (a + b) % k == e && c == f) { ok++; } //take C if (a == d && b == e && (b + c) % k == f) { ok++; } starter.push_back(ok); } } vector<long long> ans = powered(starter, n); long long final_ans = 0; REP(i, k* k* k) { int now = i; int a = now % k; now /= k; int b = now % k; now /= k; int c = now % k; REP(j, k * k * k) { now = j; int d = now % k; now /= k; int e = now % k; now /= k; int f = now % k; if (d == 0 && e == 0 && f == 0) { //候補 if (c == 0) { final_ans += ans[i * k * k * k + j]; final_ans %= MAX_MOD; } } } } cout << final_ans << endl; return 0; }