【题目链接】

点击打开链接

【算法】

要求 A^1 + A^2 + A^3 + ... + A^k

考虑通过二分来计算这个式子 :

令f(k) = A^1 + A^2 + A ^ 3 + ... + A^k

那么,当k为奇数时,f(k) = f(k-1) + A ^ k

当k为偶数时,f(k) = f(n/2) + A ^ (n/2) * f(n/2)

因此,可以通过二分 + 矩阵乘法快速幂的方式,在O(n^3log(n)^2)的时间内解决此题

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 35 int i,j,n,k,m;
struct Matrix
{
int mat[MAXN][MAXN];
} a,ans; inline Matrix add(Matrix a,Matrix b)
{
int i,j;
Matrix ans;
memset(ans.mat,,sizeof(ans.mat));
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
ans.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % m;
}
}
return ans;
}
inline Matrix mul(Matrix a,Matrix b)
{
int i,j,k;
Matrix ans;
memset(ans.mat,,sizeof(ans.mat));
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
for (k = ; k <= n; k++)
{
ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
}
}
}
return ans;
}
inline Matrix power(Matrix a,int m)
{
Matrix ans,p = a;
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
ans.mat[i][j] = (i == j);
}
}
while (m > )
{
if (m & ) ans = mul(ans,p);
p = mul(p,p);
m >>= ;
}
return ans;
}
Matrix solve(int n)
{
Matrix tmp;
if (n == ) return a;
if (n % == )
{
tmp = solve(n/);
return add(tmp,mul(power(a,n/),tmp));
} else return add(solve(n-),power(a,n));
} int main()
{ scanf("%d%d%d",&n,&k,&m);
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
scanf("%d",&a.mat[i][j]);
}
}
ans = solve(k);
for (i = ; i <= n; i++)
{
for (j = ; j < n; j++)
{
printf("%d ",ans.mat[i][j]);
}
printf("%d\n",ans.mat[i][n]);
} return ; }

最新文章

  1. Oracle 12c 使用scott等普通用户的方法
  2. Bloomberg面经准备: Josephus problem
  3. 递归算法(三)&mdash;&mdash;多项分布问题
  4. 关于mysql中int(1)中int后面的数字
  5. mac基本用法
  6. ActiveX相关
  7. 它们的定义TextView使之具有跑马灯的效果
  8. PHP进口Excel至MySQL方法
  9. SSH-KeyGen 的用法
  10. linux系统下Python虚拟环境的安装和使用
  11. Django之MVC和MTV
  12. VS2012创建ATL工程及使用MFC测试COM组件
  13. apache安装配置
  14. 纸牌屋第一季/全集House of Cards迅雷下载
  15. 打开Word时出现“The setup controller has encountered a problem during install. Please ...”什么意思
  16. Linux命令之乐--wget
  17. Texas Instruments matrix-gui-2.0 hacking -- menubar.php
  18. C语言发送邮件
  19. Java中的语法树结构
  20. 20145222黄亚奇《网络对抗》- shellcode注入&amp;Return-to-libc攻击深入

热门文章

  1. 树莓派-3 启用root
  2. Python多线程豆瓣影评API接口爬虫
  3. vector元素的删除 remove的使用 unique的使用
  4. poj 3648 2-sat 输出任意一组解模板
  5. POJ 3233_Matrix Power Series
  6. CLR运行机制
  7. Ubuntu 16.04出现Can&#39;t open /etc/rc.d/init.d/functions的问题解决
  8. oracle的processes和session最大限制
  9. [转]Attribute在.net编程中的应用
  10. [React] Use Prop Collections with Render Props