Panic! at the Disco SOLUTION PANIC

Page Contents

Panic! at the Disco November Challenge 2020

You are given a K×K matrix M. For each r and c (1≤r,c≤K), let’s denote the element in the r-th row and c-th column by Mr,c. You are also given three integers N, a and d. Let’s define a K×K matrix
S=∑i=0NFa+i⋅d⋅Mi.
Here, M0 is the identity matrix and for any non-negative integer i, Fi is the i-th Fibonacci number ― formally, F0=0, F1=1 and Fi=Fi−1+Fi−2 for i>1.
Let’s denote elements of the matrix S in the same way as for M. For each valid r and c, compute Sr,c modulo 998,244,353.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains four space-separated integers K, a, d and N.
K lines follow. For each valid i, the i-th of these lines contains K space-separated integers Mi,1,Mi,2,…,Mi,K.
Output
For each test case, print K lines. For each valid i, the i-th of these lines should contain K space-separated integers Si,1,Si,2,…,Si,K modulo 998,244,353.
Constraints
1≤T≤100
1≤K≤100
0≤a,d≤109
0≤N≤101,000
0≤Mi,j<998,244,353 for each valid i and j
the sum of K over all test cases does not exceed 100
K=1
N≤1018
K≤20
N≤1018
Subtask #3 (60 points): original constraints
Example Input
3
1 0 2 4
1
2 3 4 5
1 0
0 1
3 23 45 107
5 7 2
1 8 9
3 4 5
Example Output
33
33552 0
0 33552
601338635 934201293 356700741
960409891 125261415 197093893
136328022 287118456 122438416
SOLUTION:  credit to : krijgertje

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <list>
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
#include <array>
using namespace std;

#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define FORSZ(i,a,v) FOR(i,a,SZ(v))
#define REPSZ(i,v) REP(i,SZ(v))
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXDIM = 100;
const int MOD = 998244353;
void inc(int& a, int b) { if ((a += b) >= MOD) a -= MOD; }
typedef vector<vector<int>> Mat;

int dim, fiboffset, fibstep; ll mxp;
Mat A;
Mat ans;

Mat mmult(const Mat& A, const Mat& B) {
int dim = SZ(A); assert(dim >= 1 && SZ(A[0]) == dim && SZ(B) == dim && SZ(B[0]) == dim);
Mat C(dim, vector<int>(dim, 0));
REP(i, dim) REP(j, dim) REP(k, dim) C[i][j] = (C[i][j] + (ll)A[i][k] * B[k][j]) % MOD;
return C;
}
Mat madd(const Mat& A, const Mat& B) {
int dim = SZ(A); assert(dim >= 1 && SZ(A[0]) == dim && SZ(B) == dim && SZ(B[0]) == dim);
Mat C = A; REP(i, dim) REP(j, dim) inc(C[i][j], B[i][j]); return C;
}

Mat mpow(Mat A, ll n) {
int dim = SZ(A); assert(dim >= 1 && SZ(A[0]) == dim);
Mat ret(dim, vector<int>(dim, 0)); REP(i, dim) ret[i][i] = 1;
while (true) { if (n & 1) ret = mmult(ret, A); if ((n >>= 1) == 0) return ret; A = mmult(A, A); }
}

Mat zero(int dim) { Mat ret(dim, vector<int>(dim, 0)); return ret; }
Mat ident(int dim) { Mat ret(dim, vector<int>(dim, 0)); REP(i, dim) ret[i][i] = 1; return ret; }
pair<Mat, Mat> msumpow(const Mat& A, ll n) { // (A^n,sum(A^i)) for i<n
int dim = SZ(A); assert(dim >= 1 && SZ(A[0]) == dim);
if (n == 0) return MP(ident(dim), zero(dim));
if (n % 2 == 1) {
pair<Mat, Mat> sub = msumpow(A, n – 1);
} else {
pair<Mat, Mat> sub = msumpow(A, n / 2);
return MP(mmult(sub.first, sub.first), mmult(sub.second, madd(ident(dim), sub.first)));
}
}

void printmat(char* name, const Mat& A) {
printf(“%sn”, name);
REPSZ(i, A) { REPSZ(j, A[i]) { if (j != 0) printf(” “); printf(“%d”, A[i][j]); } puts(“”); }
}

void solve() {
Mat F(2, vector<int>(2));
F[0][0] = 0, F[0][1] = 1, F[1][0] = 1, F[1][1] = 1;
Mat Foffset = mpow(F, fiboffset);
Mat Fstep = mpow(F, fibstep);
Mat B(2 * dim, vector<int>(2 * dim));
REP(i, dim) REP(j, dim) REP(ii, 2) REP(jj, 2) B[ii * dim + i][jj * dim + j] = (ll)Fstep[ii][jj] * A[i][j] % MOD;
Mat D = msumpow(B, mxp + 1).second;
ans = Mat(dim, vector<int>(dim));
REP(i, dim) REP(j, dim) {
int x = D[i][j + dim], y = D[i + dim][j + dim];
ans[i][j] = ((ll)x * Foffset[0][0] + (ll)y * Foffset[0][1]) % MOD;
}
}

void run() {
scanf(“%d%d%d%lld”, &dim, &fiboffset, &fibstep, &mxp);
A = Mat(dim, vector<int>(dim)); REP(i, dim) REP(j, dim) scanf(“%d”, &A[i][j]);
solve();
REPSZ(i, ans) { REPSZ(j, ans[i]) { if (j != 0) printf(” “); printf(“%d”, ans[i][j]); } puts(“”); }
}

int main() {
int ncase; scanf(“%d”, &ncase); FORE(i, 1, ncase) run();
return 0;
}