rt.

做矩阵乘法的时候开了一个这样的矩阵：

struct matrix {
	static const int N=5e3+5;
	int c[N][N];
	matrix() {
		rep(i,1,m) {
			rep(j,1,m)
				c[i][j]=0;
		}
	}
	void init() {
		rep(i,1,m)
			c[i][i]=1;
	}
	matrix operator * (const matrix &tmp) const {
		matrix res;
		rep(i,1,m) {
			rep(k,1,m) {
				rep(j,1,m)
					add(res.c[i][j],1ll*c[i][k]*tmp.c[k][j]%MOD);
			}
		}
		return res;
	}
};
matrix qpow(matrix &a,ll b) {
	matrix res,base=a; 
	res.init();
	while(b) {
		if(b&1)
			res=res*base;
		base=base*base; b>>=1;
	}
	return res;
}

然后调用 qpow 时非常非常慢（大概在 $3000\text{ms}$ 左右），甚至去掉 matrix &a 的 & 会导致 RE，但是我测了一下实际 operator * 部分的速度，却跑得很快，只有 $1\sim 5\text{ms}$ 左右（$m$ 基本上只有 $1\sim200$ 的范围，对于样例，只有 $1\sim 3$ 的范围）。

然后我将 static const int N=5e3+5; 改成 static const int N=2e2+5;，运行速度就会非常快，只有 $3\text{ms}$ 左右。

和同学们讨论了一下，可能有下面几种可能：

• 在 operator * 里内存指针移动太大/申请空间需要时间。但是实测 opertoar * 运行时间很短。
• 传值时花费了时间。但是所有参数传递均使用传地址，应当是不需要时间的。

求助谷民为什么/kel

完整代码见：https://www.luogu.com.cn/paste/c4bm8tg0。

样例见：https://www.luogu.com.cn/paste/oc1yx8tj。