Spring-1-I 233 Matrix(HDU 5015)解题报告及测试数据
233 Matrix
Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333...) Besides, in 233 matrix, we got a i,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,...,a n,0, could you tell me a n,m in the 233 matrix?
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).
Output
For each case, output a n,m mod 10000007.
Sample Input
1 1
1
2 2
0 0
3 7
23 47 16
Sample Output
234
2799
72937
Hint
题解:
数字范围很大,必须用long long 整型,不然会WA。
构造矩阵时需要注意233的增长2333=233*10+3。一般情况下,递推的矩阵都可以用使用矩阵快速幂来解决。
求快速幂的时候,需要注意当前幂指数为奇数的时候的处理。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <sstream>
#include <queue>
#include <stack>
#include <stack>
#include <map>
using namespace std; #define F(i,s,e) for(int i = s;i<e;i++)
#define FA(i,s,e) for(int i=s;i>e;i--)
#define ss(x) scanf("%d",&x)
#define s64(x) scanf("%I64d",&x)
#define write() freopen("1.in","r",stdin)
#define W(x) while(x)
typedef long long LL; int aa[15];
int N;
const int Mod = 10000007;
struct Matrix{
LL m[15][15];
Matrix(){
memset(m,0,sizeof(m));
}
}; void init(Matrix&a,int n){//构造初始矩阵
N = n+2;
F(i,0,N)F(j,0,N)a.m[i][j]=0;
F(i,0,n)FA(j,n-1,i-1)a.m[i][j]=1;
F(i,0,n)a.m[n][i]=1;
a.m[n][n]=10;
a.m[n+1][n]=3;
a.m[n+1][n+1]=1;
}
Matrix mul(Matrix a,Matrix b){//矩阵乘法
Matrix c;
F(i,0,N)
F(j,0,N)
F(k,0,N)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]) % Mod;
return c;
}
Matrix power_m(Matrix a,int m){//矩阵快速幂
Matrix b;
F(i,0,N)b.m[i][i]=1;
W(m){
if(m%2)b = mul(a,b);//如果是奇数,则先乘出
a = mul(a,a);
m = m/2;
}
return b;
}
int main(){
//write();
int n,m;
LL ans;
Matrix a,b;
W(ss(n)!=EOF){
ss(m);
F(i,0,n)ss(aa[i]);
aa[n]=233;aa[n+1]=1;
ans =0;
init(a,n);
b = power_m(a,m);
F(i,0,N)ans=(ans+aa[i]*b.m[i][n-1])%Mod;//计算右下角的值
printf("%I64d\n",ans);
}
}
最新文章
- arch下的启动问题解决
- 【转】七种常见阈值分割代码(Otsu、最大熵、迭代法、自适应阀值、手动、迭代法、基本全局阈值法)
- jQuery小技巧
- MS10048依旧是Windows 2003 x86 的杀器
- fancybox去除不受待见的水平滚动条
- WPF数据双向绑定
- 使用JSON的数据格式
- php 数组排序 (转)
- UIBezierPath和CAShapeLayer的关系
- Windows下MongoDB常用命令
- How to verify Certificate Pinning?
- Python模块探秘之EasyGui
- [Linux] Vim 撤销 回退 操作
- python numpy 科学计算通用函数汇总
- Tars 负载均衡
- C# 利用ZXing.Net来生成条形码和二维码
- Visual Studio 2013 配置多个Release版本,并为每个版本配置预编译的宏
- 永久修改VS include目录
- poj-2154-polya+euler函数
- Percona Toolkit之pt-table-checksum学习