233 Matrix
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1190 Accepted Submission(s): 700
Problem Description
Input
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 109). The second line contains n integers, a1,0,a2,0,...,an,0(0 ≤ ai,0 < 231).
Output
Sample Input
Sample Output
Hint
我们这样看:已知a11 ,a21 ,a31 ,a41 。。。求后面的
a12 = a11 +233;
a22 = a11 + a21 +233;
a32 = a11 + a21 +a31 +233;
a42 = a11 + a21 +a31 +a41 +233;
.........
同理:后面的列也一样:
a13 = a12 +233;
a23 = a12 + a22 +233;
a33 = a12 + a22 +a32 +233;
a43 = a12 + a22 +a32 +a42 +233;
...........
ss所以有矩阵:
233 | a11 |
a21 | a31 | a41 | ... | 3 |
*
10 | 1 | 1 | 1 | 1 | ... | 0 |
0 | 1 | 1 | 1 | 1 | ... | 0 |
0 | 0 | 1 | 1 | 1 | ... | 0 |
0 | 0 | 0 | 1 | 1 | ... | 0 |
0 | 0 | 0 | 0 | 1 | ... | 0 |
... | ... | ... | ... | ... | ... | ... |
1 | 0 | 0 | 0 | 0 | ... | 1 |
=
......................................................................................................................................................
z转载请注明出处:寻找&星空の孩子
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5015
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL __int64
#define mod 10000007 LL N,M; struct matrix
{
LL m[][];
};
LL a[]; matrix multiply(matrix x,matrix y)
{
matrix temp;
memset(temp.m,,sizeof(temp.m));
for(int i=; i<N+; i++)
{
for(int j=; j<N+; j++)
{
if(x.m[i][j]==) continue;
for(int k=; k<N+; k++)
{
if(y.m[j][k]==) continue;
temp.m[i][k]+=x.m[i][j]*y.m[j][k]%mod;
temp.m[i][k]%=mod;
}
}
}
return temp;
} matrix quickmod(matrix a,LL n)
{
matrix res;
memset(res.m,,sizeof(res.m));
for(int i=;i<N+;i++) res.m[i][i]=;
while(n)
{
if(n&)
res=multiply(res,a);
n>>=;
a=multiply(a,a);
}
return res;
}
int main()
{
int n,k;
while(scanf("%d%d",&N,&M)!=EOF)
{
a[]=;
a[N+]=;
for(int i=;i<=N;i++)
{
scanf("%d",&a[i]);
} matrix ans;
memset(ans.m,,sizeof(ans.m));
ans.m[][]=;
ans.m[N+][]=;
ans.m[N+][N+]=;
for(int j=;j<=N;j++)
{
for(int i=;i<=j;i++)
{
ans.m[i][j]=;
}
} ans=quickmod(ans,M);//M次幂定位到纵坐标。 LL ant=;
for(int i=;i<N+;i++)//横坐标是N,即,乘以矩阵的N列。
{
ant=(ant+a[i]*ans.m[i][N])%mod;
}
printf("%I64d\n",ant);
}
return ;
}
本来要做新题的,可是遇到不会的了。。。hdu4767 Bell 现在卡在 中国剩余定理,还要好好梳理梳理!
加油!少年!!!
233 Matrix(hdu5015 矩阵)的更多相关文章
-
ACM学习历程——HDU5015 233 Matrix(矩阵快速幂)(2014陕西网赛)
Description In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 2 ...
-
hdu 5015 233 Matrix (矩阵高速幂)
233 Matrix Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Tota ...
-
hdu 5015 233 Matrix(构造矩阵)
http://acm.hdu.edu.cn/showproblem.php?pid=5015 由于是个二维的递推式,当时没有想到能够这样构造矩阵.从列上看,当前这一列都是由前一列递推得到.依据这一点来 ...
-
HDU5015 233 Matrix(矩阵高速幂)
HDU5015 233 Matrix(矩阵高速幂) 题目链接 题目大意: 给出n∗m矩阵,给出第一行a01, a02, a03 ...a0m (各自是233, 2333, 23333...), 再给定 ...
-
HDU5015 233 Matrix —— 矩阵快速幂
题目链接:https://vjudge.net/problem/HDU-5015 233 Matrix Time Limit: 10000/5000 MS (Java/Others) Memor ...
-
[HDU5015]233 Matrix
[HDU5015]233 Matrix 试题描述 In our daily life we often use 233 to express our feelings. Actually, we ma ...
-
233 Matrix(矩阵快速幂+思维)
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233 ...
-
HDU 5015 233 Matrix(网络赛1009) 矩阵快速幂
先贴四份矩阵快速幂的模板:http://www.cnblogs.com/shangyu/p/3620803.html http://www.cppblog.com/acronix/archive/20 ...
-
233 Matrix 矩阵快速幂
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233 ...
随机推荐
-
抛弃jQuery:DOM API之选择元素
原文链接:http://blog.garstasio.com/you-dont-need-jquery/selectors/ 我的Blog:http://cabbit.me/you-dont-need ...
-
《大话移动APP测试:Android与iOS应用测试指南》
<大话移动app测试:android与ios应用测试指南> 基本信息 作者: 陈晔 出版社:清华大学出版社 ISBN:9787302368793 上架时间:2014-7-7 出版日期:20 ...
-
DBCP连接池介绍
DBCP连接池介绍 ----------------------------- 目前 DBCP 有两个版本分别是 1.3 和 1.4. DBCP 1.3 版本需要运行于 JDK 1.4-1.5 ,支持 ...
-
.net转php laraval框架学习系列(四) 项目实战---View
laravel的参考文档中view的讲解有些简单. 在实际项目开发中view的灵活性其实是非常大. 首先来看看laravel中的布局页 和asp.net mvc中有什么不同 <!DOCTYPE ...
-
Hibernate之关联关系映射(一对一主键映射和一对一外键映射)
1:Hibernate的关联关系映射的一对一外键映射: 1.1:第一首先引包,省略 1.2:第二创建实体类: 这里使用用户信息和身份证信息的关系,用户的主键编号既可以做身份证信息的主键又可以做身份证信 ...
-
android轮播图的实现原理
1.轮播图的点:RadioGroup,根据网络请求的数据,解析得到的图片的个数,设置RadioGroup的RadioButton的个数. 2.轮播图的核心技术:用Gallery来存放图片,设置适配器. ...
-
MyChatRoom——C#自制聊天室
一个用C#编写的基于Socket的Windows版聊天室,包括服务端和客户端.当服务端启动服务后,客户端可以连接到服务端,给服务端发送数据,服务端可以接收数据:服务端可以给客户端发送数据,客户端接收: ...
-
solr java demo 基础入门
<!--solr的maven依赖--> <dependencies> <dependency> <groupId>org.apache.solr&l ...
-
FrameWork数据权限浅析3之基于角色的配置表实现行级数据安全
带着上一次笔记的疑问和些许欢喜来到了混混沌沌的下午,程序员的脑子一直在不停的思索着,而多思考总是没错的,盼望着盼望着事情就有了转机,现在我们就来说一说基于角色级别的中间表机制实现行级数据安全. 由于本 ...
-
【转】Python 数据库连接池
python编程中可以使用pymysql进行数据库连接及增删改查操作,但每次连接mysql请求时,都是独立的去请求访问,比较浪费资源,而且访问数量达到一定数量时,对mysql的性能会产生较大的影响.因 ...