点击打开poj 3150
思路: 矩阵快速幂
分析:
1 题目给定n个数每个数在0~m-1之内,题目规定两个数之间的距离为min(|i-j| , n-|i-j|)。现在给定d和k,表示做k次的变换,每一次变换过后每个数变成了一个新的数。这个新的数等于和它距离小于等于d的所有数的和%m
2 这题和之前做的两道题很像hdu2276 和 FZU1692,都是属于循环同构的问题
那么我们先来看一下每个数在做一次变换过后变成什么。因为要距离小于等于d,第一种|i-j| = d , 则j = i+d , 第二种情况n-|i-j| = d , 因此 j = n-d+i 。
第一个数等于 = num[1]+num[2]+....+num[d+1]
+ num[n-d+1]+...+num[n]
第二个数等于 = num[2]+....+num[d+2]+num[n-d+2]+...+num[n]
..............................................................................................................
3 因为这里的矩阵是循环同构的,因此我们只要求出第一行,剩下的我们就可以根据前一行推出。这样就把矩阵的乘法的复杂度降到了O(n^2)
代码:
/************************************************
* 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 = 505;
int n , MOD , d , k;
int arr[N];
struct Matrix{
int64 mat[N][N];
Matrix operator*(const Matrix &m)const{
Matrix tmp;
for(int i = 1 ; i <= n ; i++){
tmp.mat[1][i] = 0;
for(int j = 1 ; j <= n ; j++)
tmp.mat[1][i] += mat[1][j]*m.mat[j][i]%MOD;
tmp.mat[1][i] %= MOD;
}
for(int i = 2 ; i <= n ; i++){
tmp.mat[i][1] = tmp.mat[i-1][n];
for(int j = 2 ; j <= n ; j++)
tmp.mat[i][j] = tmp.mat[i-1][(j-1+n)%n];
}
return tmp;
}
};
void init(Matrix &m){
memset(m.mat , 0 , sizeof(m.mat));
for(int i = 1 ; i <= d+1 ; i++)
m.mat[1][i] = 1;
for(int i = n-d+1 ; i <= n ; i++)
m.mat[1][i] = 1;
for(int i = 2 ; i <= n ; i++){
m.mat[i][1] = m.mat[i-1][n];
for(int j = 2 ; j <= n ; j++)
m.mat[i][j] = m.mat[i-1][(j-1+n)%n];
}
}
void Pow(Matrix &m){
Matrix ans;
memset(ans.mat , 0 , sizeof(ans.mat));
for(int i = 1 ; i <= n ; i++)
ans.mat[i][i] = 1;
while(k){
if(k&1)
ans = ans*m;
k >>= 1;
m = m*m;
}
for(int i = 1 ; i <= n ; i++){
int64 sum = 0;
for(int j = 1 ; j <= n ; j++)
sum += ans.mat[i][j]*arr[j]%MOD;
if(i > 1) printf(" ");
printf("%lld" , sum%MOD);
}
puts("");
}
int main(){
Matrix m;
while(scanf("%d" , &n) != EOF){
scanf("%d%d%d" , &MOD , &d , &k);
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &arr[i]);
init(m);
Pow(m);
}
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题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码