233 Matrix(hdu5015 矩阵)

时间:2022-03-14 17:04:59

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

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 a0,1 = 233,a0,2 = 2333,a0,3 = 23333...) Besides, in 233 matrix, we got ai,j = ai-1,j +ai,j-1( i,j ≠ 0). Now you have known a1,0,a2,0,...,an,0, could you tell me an,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 ≤ 109). The second line contains n integers, a1,0,a2,0,...,an,0(0 ≤ ai,0 < 231).

 

Output

For each case, output an,m mod 10000007.
 

Sample Input

1 1
1
2 2
0 0
3 7
23 47 16
 

Sample Output

234
2799
72937
 
 
 
 
 

Hint

233 Matrix(hdu5015 矩阵)

我们这样看:已知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转载请注明出处:233 Matrix(hdu5015 矩阵)寻找&星空の孩子

题目链接: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 矩阵)的更多相关文章

  1. ACM学习历程——HDU5015 233 Matrix(矩阵快速幂)(2014陕西网赛)

    Description In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 2 ...

  2. hdu 5015 233 Matrix (矩阵高速幂)

    233 Matrix Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Tota ...

  3. hdu 5015 233 Matrix&lpar;构造矩阵&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=5015 由于是个二维的递推式,当时没有想到能够这样构造矩阵.从列上看,当前这一列都是由前一列递推得到.依据这一点来 ...

  4. HDU5015 233 Matrix&lpar;矩阵高速幂&rpar;

    HDU5015 233 Matrix(矩阵高速幂) 题目链接 题目大意: 给出n∗m矩阵,给出第一行a01, a02, a03 ...a0m (各自是233, 2333, 23333...), 再给定 ...

  5. HDU5015 233 Matrix —— 矩阵快速幂

    题目链接:https://vjudge.net/problem/HDU-5015 233 Matrix Time Limit: 10000/5000 MS (Java/Others)    Memor ...

  6. &lbrack;HDU5015&rsqb;233 Matrix

    [HDU5015]233 Matrix 试题描述 In our daily life we often use 233 to express our feelings. Actually, we ma ...

  7. 233 Matrix&lpar;矩阵快速幂&plus;思维&rpar;

    In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233 ...

  8. HDU 5015 233 Matrix(网络赛1009) 矩阵快速幂

    先贴四份矩阵快速幂的模板:http://www.cnblogs.com/shangyu/p/3620803.html http://www.cppblog.com/acronix/archive/20 ...

  9. 233 Matrix 矩阵快速幂

    In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233 ...

随机推荐

  1. 抛弃jQuery:DOM API之选择元素

    原文链接:http://blog.garstasio.com/you-dont-need-jquery/selectors/ 我的Blog:http://cabbit.me/you-dont-need ...

  2. 《大话移动APP测试:Android与iOS应用测试指南》

    <大话移动app测试:android与ios应用测试指南> 基本信息 作者: 陈晔 出版社:清华大学出版社 ISBN:9787302368793 上架时间:2014-7-7 出版日期:20 ...

  3. DBCP连接池介绍

    DBCP连接池介绍 ----------------------------- 目前 DBCP 有两个版本分别是 1.3 和 1.4. DBCP 1.3 版本需要运行于 JDK 1.4-1.5 ,支持 ...

  4. &period;net转php laraval框架学习系列(四) 项目实战---View

    laravel的参考文档中view的讲解有些简单. 在实际项目开发中view的灵活性其实是非常大. 首先来看看laravel中的布局页 和asp.net mvc中有什么不同 <!DOCTYPE ...

  5. Hibernate之关联关系映射&lpar;一对一主键映射和一对一外键映射&rpar;

    1:Hibernate的关联关系映射的一对一外键映射: 1.1:第一首先引包,省略 1.2:第二创建实体类: 这里使用用户信息和身份证信息的关系,用户的主键编号既可以做身份证信息的主键又可以做身份证信 ...

  6. android轮播图的实现原理

    1.轮播图的点:RadioGroup,根据网络请求的数据,解析得到的图片的个数,设置RadioGroup的RadioButton的个数. 2.轮播图的核心技术:用Gallery来存放图片,设置适配器. ...

  7. MyChatRoom——C&num;自制聊天室

    一个用C#编写的基于Socket的Windows版聊天室,包括服务端和客户端.当服务端启动服务后,客户端可以连接到服务端,给服务端发送数据,服务端可以接收数据:服务端可以给客户端发送数据,客户端接收: ...

  8. solr java demo 基础入门

      <!--solr的maven依赖--> <dependencies> <dependency> <groupId>org.apache.solr&l ...

  9. FrameWork数据权限浅析3之基于角色的配置表实现行级数据安全

    带着上一次笔记的疑问和些许欢喜来到了混混沌沌的下午,程序员的脑子一直在不停的思索着,而多思考总是没错的,盼望着盼望着事情就有了转机,现在我们就来说一说基于角色级别的中间表机制实现行级数据安全. 由于本 ...

  10. 【转】Python 数据库连接池

    python编程中可以使用pymysql进行数据库连接及增删改查操作,但每次连接mysql请求时,都是独立的去请求访问,比较浪费资源,而且访问数量达到一定数量时,对mysql的性能会产生较大的影响.因 ...