洛谷 P1939 【模板】矩阵加速(数列)
2024-08-29 23:53:24
题目描述
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007(10^9+7)取余的值。
输入输出格式
输入格式:
第一行一个整数T,表示询问个数。
以下T行,每行一个正整数n。
输出格式:
每行输出一个非负整数表示答案。
输入输出样例
输入样例#1:
3
6
8
10
输出样例#1:
4
9
19
说明
对于30%的数据 n<=100;
对于60%的数据 n<=2*10^7;
对于100%的数据 T<=100,n<=2*10^9;
题解:
其实这篇本来想写日记的,但是老师突然来到了我的身边,我就迅速把这道刚做完的题粘到了这里。
有始有终,就写吧。
谁可以告诉我,为什么我的暴力没有分!
众人OS:你错了呗。
#include <cstdio>
#include <cstring>
using namespace std; typedef long long LL;
const int mod=1e9+;
int T, n;
LL tmp[][]={{,,},{,,},{,,}}; struct Matrix33{
LL mat[][];
Matrix33 operator *(Matrix33 b){
Matrix33 m;
for (int i=; i<; ++i) for (int j=; j<; ++j){
m.mat[i][j]=;
for (int k=; k<; ++k)
m.mat[i][j]=(m.mat[i][j]+(mat[i][k]*b.mat[k][j]%mod))%mod;
}
return m;
}
}beg, unit, plus; Matrix33 get_mat(int n){
memcpy(plus.mat, tmp, sizeof(tmp));
Matrix33 ans=unit;
while (n){
if (n&) ans=ans*plus;
plus=plus*plus;
n>>=;
}
return ans;
} int main(){
unit.mat[][]=unit.mat[][]=unit.mat[][]=;
beg.mat[][]=beg.mat[][]=beg.mat[][]=;
scanf("%d", &T);
for (int tt=; tt<T; ++tt){
scanf("%d", &n);
if (n<) printf("1\n");
else printf("%lld\n", (beg*get_mat(n-)).mat[][]);
}
return ;
}
AC
一世安宁
最新文章
- C#与数据库访问技术总结(十四)之DataAdapter对象
- Flash Media Server 4.5 序列号 (fms4.5 激活码)
- 3DES封装类
- [翻译] java NIO 教程---介绍
- centos6.4添加fedora-epel源
- ANDROID STUDIO, GRADLE AND NDK INTEGRATION
- leetcode:Rotate Array
- 记录一点自己写的Php代码(1)取得任意种类,无限级下线
- Android实现弹出输入法时,顶部固定,中间部分上移的效果
- Bootstrap_Javascript_固定定位
- char varchar varchar2 的区别 (转)
- win10提示管理员已阻止你运行此应用,如何强制运行
- ACSA Associate -- 01 Introduction To The Course
- 关于post利用之Python
- matlab中fix函数,floor函数,ceil函数
- Kaldi阅读并更改代码
- Ex3_2 最近点对
- 某公司面试java试题之【一】,看看吧,说不定就是你将要做的题
- Python学习之旅(十四)
- Python之groupby