传送门
emm
没错这就是矩阵快速幂的裸体板子题
所以
没什么可说的哇 qwq
- #include<cstdio>
- #include<cstring>
- #define ll long long
- using namespace std;
- const ll mod = 1e9+7;
- ll n,k;
- struct mat
- {
- ll m[105][105];
- }l,r;
- mat mul(mat x,mat y)
- {
- mat sum;
- for(int i = 1;i <= n;i++)
- for(int j = 1;j <= n;j++)
- sum.m[i][j] = 0;
- for(int i = 1;i <= n;i++)
- for(int j = 1;j <= n;j++)
- for(int k = 1;k <= n;k++)
- sum.m[i][j] = (sum.m[i][j]%mod +(x.m[i][k] * y.m[k][j])% mod)% mod;
- return sum;
- }
- mat qpow(mat x,ll y)
- {
- mat ans = r;
- while(y)
- {
- if(y & 1)
- ans = mul(ans,x);
- x = mul(x,x);
- y>>= 1;
- }
- return ans;
- }
- int main()
- {
- scanf("%lld%lld",&n,&k);
- for(int i = 1;i <= n;i++)
- for(int j = 1;j <= n;j++)
- scanf("%lld",&l.m[i][j]);
- for(int i = 1;i <= n;i++)
- r.m[i][i] = 1;
- mat ans = qpow(l,k);
- for(int i = 1;i <= n;i++)
- {
- for(int j = 1;j <= n;j++)
- printf("%lld",ans.m[i][j]);
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3009269.html