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