結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
![]() |
提出日時 | 2025-08-22 22:33:53 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 349 ms / 2,000 ms |
コード長 | 1,290 bytes |
コンパイル時間 | 928 ms |
コンパイル使用メモリ | 27,728 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-22 22:33:56 |
合計ジャッジ時間 | 1,965 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
コンパイルメッセージ
main.c: In function ‘solve’: main.c:29:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 29 | scanf("%lld", &n); | ^~~~~~~~~~~~~~~~~ main.c: In function ‘main’: main.c:60:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | scanf("%d", &t); | ^~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> long long int modpow(long long int a, long long int n, long long int p) { long long int res = 1; for (; n > 0; n /= 2, a = a * a % p) if (n % 2 > 0) res = res * a % p; return res; } void chmul(long long int a[7][7], long long int b[7][7], long long int p) { long long int c[7][7]; long long int i, j, k; for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) c[i][j] = 0; for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) for (k = 0; k < 7; k++) c[i][j] += a[i][k] * b[k][j] % p; for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) a[i][j] = c[i][j] % p; return; } void solve() { long long int n; scanf("%lld", &n); long long int A[7][7] = { {1,1,0,0,1,1,1}, {1,1,0,0,0,0,0}, {1,1,1,1,0,0,0}, {1,1,1,1,0,0,0}, {0,0,1,1,1,1,0}, {0,0,1,1,1,1,0}, {0,0,0,0,1,1,1} }; long long int res[7][7] = { {1,0,0,0,0,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,0,0,1,0,0}, {0,0,0,0,0,1,0}, {0,0,0,0,0,0,1} }; const long long int p = 998244353; long long int ans = p - modpow(2, n - 1, p); for (; n > 0; n /= 2, chmul(A, A, p)) if (n % 2 > 0) chmul(res, A, p); ans = (ans + res[0][0]) % p; printf("%lld\n", ans); return; } int main() { int t; scanf("%d", &t); for (; t > 0; t--) solve(); return 0; }