@[RNTBW](/user/643735) 考虑将转移矩阵的倍增存下来，每次询问时令初始向量逐个左乘转移矩阵的倍增，将时间复杂度降至 $O(a^3\log n+Ta^2\log n)$
by reveal @ 2023-03-21 07:07:28
@[RNTBW](/user/643735) $O(Ta^3\log n) = O(2 \times 10^6 \log 10^{18})$，会被卡吧。
by E1_de5truct0r @ 2023-03-21 07:19:58
@[reveal](/user/523491) 能给出代码吗？谢谢
by RNTBW @ 2023-03-21 08:00:04
@[RNTBW](/user/643735) 随便卡卡肯定能过吧
```cpp
const unsigned int mod=998244353;
struct matrix
{
unsigned long long f[(1<<8)+25][(1<<8)+25];
};
struct Matrix
{
unsigned long long f[(1<<8)+25];
};
unsigned int N;
inline matrix operator *(const matrix &A,const matrix &B)
{
static unsigned long long a[(1<<8)+25][(1<<8)+25];
memcpy(a,A.f,sizeof(a));
static unsigned long long b[(1<<8)+25][(1<<8)+25];
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
b[j][i]=B.f[i][j];
}
}
static matrix ret;
for(int i=0;i<N;i++)
{
unsigned long long *A=a[i];
for(int j=0,k;j<N;j++)
{
unsigned long long *B=b[j];
unsigned long long v=0;
for(k=0;k+15<N;k+=16)
{
v=(v+A[k]*B[k]+A[k|1]*B[k|1]
+A[k|2]*B[k|2]+A[k|3]*B[k|3]
+A[k|4]*B[k|4]+A[k|5]*B[k|5]
+A[k|6]*B[k|6]+A[k|7]*B[k|7]
+A[k|8]*B[k|8]+A[k|9]*B[k|9]
+A[k|10]*B[k|10]+A[k|11]*B[k|11]
+A[k|12]*B[k|12]+A[k|13]*B[k|13]
+A[k|14]*B[k|14]+A[k|15]*B[k|15])%mod;
}
for(;k<N;k++)
{
v+=A[k]*B[k];
}
ret.f[i][j]=v%mod;
}
}
return ret;
}
inline Matrix operator *(const matrix &a,const Matrix &b)
{
static Matrix ret;
const unsigned long long *B=b.f;
for(int i=0,k;i<N;i++)
{
const unsigned long long *A=a.f[i];
unsigned long long v=0;
for(k=0;k+15<N;k+=16)
{
v=(v+A[k]*B[k]+A[k|1]*B[k|1]
+A[k|2]*B[k|2]+A[k|3]*B[k|3]
+A[k|4]*B[k|4]+A[k|5]*B[k|5]
+A[k|6]*B[k|6]+A[k|7]*B[k|7]
+A[k|8]*B[k|8]+A[k|9]*B[k|9]
+A[k|10]*B[k|10]+A[k|11]*B[k|11]
+A[k|12]*B[k|12]+A[k|13]*B[k|13]
+A[k|14]*B[k|14]+A[k|15]*B[k|15])%mod;
}
for(;k<N;k++)
{
v+=A[k]*B[k];
}
ret.f[i]=v%mod;
}
return ret;
}
inline void qpow(Matrix &S,matrix &a,unsigned int b)
{
while(b)
{
if(b&1)
{
S=a*S;
}
a=a*a,b>>=1;
}
}
```
可以稍微改改里面的数组大小
by liqingyang @ 2023-03-21 08:24:42
@[liqingyang](/user/272088) sto
by RNTBW @ 2023-03-21 08:45:12