点击打开poj 3735
思路: 矩阵快速幂
分析:
1 题目给定n只猫,每只猫的初始的花生的数量为0。现在有三种操作,g i 第i只猫加一个花生,e i 把第i只猫的所有花生全部吃完 s i j 把第i 和 j只猫的花生数进行交换
2 根据上面的三种操作那么我们能够举例n = 3的时候的三种操作。
对于g 1,我们把第一行的最后一位加1,这里增加了一列目的是为了能够求出和,因为初始化a b c都为0
1 0 0 1 a a+1
0 1 0 0 * b = b
0 0 1 0 c c
0 0 0 1 1 1
对于e 1,我们把第一行全部置为0,那么这样就是相当于吃掉全部的花生
0 0 0 0 a 0
0 1 0 0 * b = b
0 0 1 0 c c
0 0 0 1 1 1
对于 s 1 2
0 1 0 0 a b
1 0 0 0 * b = a
0 0 1 0 c c
0 0 0 1 1 1
3 那么我们只要先把k次的操作整合到一个矩阵A里面,然后求A^m,矩阵的最后一列的前n个数即为所求
4 由于矩阵乘法涉及到乘的次数越多,就越耗时间,因此我们需要在矩阵相乘的时候进行优化
代码:
/************************************************
* By: chenguolin *
* Date: 2013-08-31 *
* Address: http://blog.csdn.net/chenguolinblog *
************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int64;
const int N = 105;
int n , m , k;
struct Matrix{
int64 mat[N][N];
Matrix operator*(const Matrix& ma)const{
Matrix tmp;
for(int i = 0 ; i <= n ; i++){
for(int j = 0 ; j <= n ; j++){
tmp.mat[i][j] = 0;
for(int k = 0 ; k <= n ; k++){
if(mat[i][k] && ma.mat[k][j])
tmp.mat[i][j] += mat[i][k]*ma.mat[k][j];
}
}
}
return tmp;
}
};
void input(Matrix &ma){
char c;
int x , y;
memset(ma.mat , 0 , sizeof(ma.mat));
for(int i = 0 ; i <= n ; i++)
ma.mat[i][i] = 1;
while(k--){
scanf("%c" , &c);
if(c == 'g'){
scanf("%d%*c" , &x);
x--;
ma.mat[x][n]++;
}
else if(c == 's'){
scanf("%d%d%*c" , &x , &y);
x-- , y--;
for(int i = 0 ; i <= n ; i++){
int tmp = ma.mat[x][i];
ma.mat[x][i] = ma.mat[y][i];
ma.mat[y][i] = tmp;
}
}
else{
scanf("%d%*c" , &x);
x--;
for(int i = 0 ; i <= n ; i++)
ma.mat[x][i] = 0;
}
}
}
void Pow(Matrix &ma){
Matrix ans;
memset(ans.mat , 0 , sizeof(ans.mat));
for(int i = 0 ; i <= n ; i++)
ans.mat[i][i] = 1;
while(m){
if(m&1)
ans = ans*ma;
m >>= 1;
ma = ma*ma;
}
for(int i = 0 ; i < n ; i++){
if(i) printf(" ");
printf("%lld" , ans.mat[i][n]);
}
puts("");
}
int main(){
Matrix ma;
while(scanf("%d%d%d%*c" , &n , &m , &k) && n+m+k){
input(ma);
Pow(ma);
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。