}
}
}
return ret;
}
mat expo(mat a, int k)
{
if(k==1)return a;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i
while(k)
{
if(k&1)e=mul(a,e);
a=mul(a,a);
k>>=1;
}
return e;
}
mat add(mat a,mat b)
{
mat t;
for(int i=0;i
for(int j=0;j
t.at[i][j]=(a.at[i][j]+b.at[i][j]);
if(t.at[i][j]>=MOD){t.at[i][j]%=MOD;}
}
}
return t;
}
void print(mat ans)
{
for(int i=0;i
for(int j=0;j
if(j==0){printf("%d",ans.at[i][j]);continue;}
printf(" %d",ans.at[i][j]);
}
printf("\n");
}
}
mat sum(int k)
{
if(k==1){return d;}
if(k&1)
{
return add(sum(k-1),expo(d,k));
}
else
{
mat s=sum(k>>1);
return add(s,mul(s,expo(d,k>>1)));
}
}
int main()
{
while(~scanf("%d%d%d",&n,&k,&m))
{
MOD=m;
mat ans,t;
for(int i=0;i
for(int j=0;j
scanf("%d",&d.at[i][j]);
if(d.at[i][j]>=m)
{
d.at[i][j]%=m;
}
}
}
ans=sum(k);
print(ans);
}
return 0;
}
#include
#include
#include
using namespace std;
#define LL long long
int n,m,k;
int MOD;
struct mat {
int at[40][40];
};
mat d;
mat mul(mat a, mat b)
{
mat ret;
memset(ret.at,0,sizeof(ret.at));
for (int i=0;i
for (int k=0;k
if(a.at[i][k])
for (int j=0;j
ret.at[i][j]+=a.at[i][k]*b.at[k][j];
if(ret.at[i][j]>=MOD){ret.at[i][j]%=MOD;}
}
}
}
return ret;
}
mat expo(mat a, int k)
{
if(k==1)return a;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i
while(k)
{
if(k&1)e=mul(a,e);
a=mul(a,a);
k>>=1;
}
return e;
}
mat add(mat a,mat b)
{
mat t;
for(int i=0;i
for(int j=0;j
t.at[i][j]=(a.at[i][j]+b.at[i][j]);
if(t.at[i][j]>=MOD){t.at[i][j]%=MOD;}
}
}
return t;
}
void print(mat ans)
{
for(int i=0;i
for(int j=0;j
if(j==0){printf("%d",ans.at[i][j]);continue;}
printf(" %d",ans.at[i][j]);
}
printf("\n");
}
}
mat sum(int k)
{
if(k==1){return d;}
if(k&1)
{
return add(sum(k-1),expo(d,k));
}
else
{
mat s=sum(k>>1);
return add(s,mul(s,expo(d,k>>1)));
}
}
int main()
{
while(~scanf("%d%d%d",&n,&k,&m))
{
MOD=m;
mat ans,t;
for(int i=0;i
for(int j=0;j
scanf("%d",&d.at[i][j]);
if(d.at[i][j]>=m)
{
d.at[i][j]%=m;
}
}
}
ans=sum(k);
print(ans);
}
return 0;
}
3、poj3735
题意：有n只猫咪，开始时每只猫咪有花生0颗，现有一组操作，由下面三个中的k个操作组成：
1. g i 给i只猫咪一颗花生米
2. e i 让第i只猫咪吃掉它拥有的所有花生米
3. s i j 将猫咪i与猫咪j的拥有的花生米交换
现将上述一组操作做m次后，问每只猫咪有多少颗花生？
分析：刚开始每只猫都没有花生，所以我们要在单位矩阵上构建矩阵。给第i只猫一个花生米，那么++met[0][i]，让第i只猫吃掉所有的花生米，就令第i列清空，喵咪i与猫咪j交换花生米，就令第i列和第j列互换。矩阵就这样构造完毕，操作m次，我们就可以矩阵快速幂计算了。
[cpp]
#include
#include
#include
#define LL long long
using namespace std;
struct met{
LL at[105][105];
};
met ret,d;
LL n,m,k;
met mul(met a,met b)
{
memset(ret.at,0,sizeof(ret.at));
for(int i=0;i<=n;++i)
{
for(int k=0;k<=n;++k)
{
if(a.at[i][k])
{
for(int j=0;j<=n;++j)
{