poj 3735マトリクス行列変換

この問題は行列演算の古典的な問題である.
peanutを{0},{0},{0},{0},{1}}に初期化し、peanut行列を変換します(行変換、単位行列を操作し、左にpeanutを乗じます.列変換は右に置きます).また,マトリクスの演算は結合率に合致し,交換率に合致しない.
行列のN次方演算を行う時、私はずっとバイナリの思想を使っていないで、ずっと再帰の過程を模擬して、結果は絶えずタイムアウトして、複雑さとバイナリの思想の差は多くなくて、おかしいと感じました.後にバイナリの思想を使ってやっと過ぎた.バイナリの思想は絶えず行われる二乗の演算であり,1に出会ったら累加する.
    

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct MATRIX
{
	long long  m[110][110];
};
MATRIX mul(MATRIX num1,int n1,int m1,MATRIX num2,int n2,int m2)//m1 = n2
{
	MATRIX res;
	memset(&res, 0, sizeof(res));
	int i,j,k;
	{
		for(i = 0; i <= n1; i++)
		{
			for(k = 0; k <= m1; k++)
			{
				if(num1.m[i][k] != 0)
				{
					for(j = 0; j <= m2; j++)
					{
						res.m[i][j] += num1.m[i][k] * num2.m[k][j];

					}
				}
			}
		}
	}

	return res;
}
MATRIX POW(MATRIX num1,int k,int n)
{
	/*	int cnt = 0;
		int sta[50];
		cnt = -1;
		while(k)
		{
		if((k & 1) == 1)
		{
		sta[++cnt] = 1;
		}
		else
		{
		sta[++cnt] = 0;
		}
		k = (k >> 1);

		}
		MATRIX  res;
		cnt--;
		MATRIX first;
		memcpy(&first,&num1,sizeof(first));
		while(cnt != -1)
		{
		if(sta[cnt] == 0)
		{
		num1 = mul(num1,n,n,num1,n,n);
		}
		else
		{
		num1 = mul(num1,n,n,num1,n,n);
		num1 = mul(first,n,n,num1,n,n);
		}
		cnt--;
		}
	 *///    
	MATRIX res;
	memcpy(&res,&num1,sizeof(num1));
	memset(&res,0,sizeof(res));
	int i;
	for(i = 0; i <= n; i++)
	{
		res.m[i][i] = 1;
	}
	while(k)
	{
		if(k & 1)
		{
			res = mul(res,n,n,num1,n,n);

		}
		num1 = mul(num1,n,n,num1,n,n);
		k >>= 1;
	}//     
	return res;
}
int main()
{
	int n,k,m;
	while(scanf("%d %d %d",&n,&k,&m) != EOF)
	{
		if(n == 0 && k == 0 && m == 0)
		{
			break;
		}
		int i;
		char str[2];
		MATRIX cat;
		memset(&cat, 0, sizeof(cat));
		cat.m[n][0] = 1;
		MATRIX one;
		memset(&one, 0, sizeof(one));
		for(i = 0; i <= n; i++)
		{
			one.m[i][i] = 1;
		}
		int j;
		for(j = 0; j < m; j++)
		{
			scanf("%s",str);
			int from,to;
			if(strcmp(str,"g") == 0)
			{
				scanf("%d", &from);
				one.m[from - 1][n]++;
			}
			else if(strcmp(str,"e") == 0)
			{

				scanf("%d",&from);
				for(i = 0;i<= n; i++)
				{
					one.m[from - 1] [i] = 0;
				}
			}
			else if(strcmp(str,"s") == 0)
			{
				scanf("%d %d", &from, &to);
				from--;
				to--;
				int temp[110];
				for(i = 0 ;i <= n; i++)
				{
					temp[i] = one.m[from][i];
					one.m[from][i] = one.m[to][i];
					one.m[to][i] = temp[i];

				}
			}
		}
		one = POW(one,k,n);
		cat = mul(one,n,n,cat,n,1);
		for(i = 0; i < n; i++)
		{
			printf("%lld%c",cat.m[i][0],i==n-1? '
':' ');
		}
	}


}