| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
等差数列用二分#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int n, k, m;
struct Node{
int x[31][31];
}A;
Node Sum(Node a, Node b){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
a.x[i][j] = (a.x[i][j] + b.x[i][j])%m;
}
}
return a;
}
Node mul(Node a, Node b){
Node B;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
B.x[i][j] = 0;
for(int k = 0; k < n; ++k){
B.x[i][j] = (B.x[i][j] + a.x[i][k]*b.x[k][j]%m)%m;
}
}
}
return B;
}
Node q_m(Node AAA, Node A, ll x){
while(x){
if(x&1) AAA = mul(AAA, A);
A = mul(A, A);
x >>= 1;
}
return AAA;
}
void solve(){
Node AA, AAA, X;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
AA.x[i][j] = 0;
X.x[i][j] = AAA.x[i][j] = (i == j);
}
}
while(k > 1){
if(k&1){
AA = Sum(AA, mul(X, q_m(AAA, A, k)));
}
k >>= 1;
X = mul(Sum(AAA, q_m(AAA, A, k)), X);
}
X = Sum(mul(A, X), AA);
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
printf("%d%c", X.x[i][j], (j == n-1 ? '\n' : ' '));
}
}
}
int main(){
while(~scanf("%d%d%d", &n, &k, &m)){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
scanf("%d", &A.x[i][j]);
}
}
solve();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator