网站建设修饰商品,wordpress无法将图片上传,北京平面设计工作室,鸿星尔克网络营销题目描述 a[1]a[2]a[3]1 a[x]a[x-3]a[x-1] (x3) 求a数列的第n项对1000000007#xff08;10^97#xff09;取余的值。 输入输出格式 输入格式#xff1a; 第一行一个整数T#xff0c;表示询问个数。 以下T行#xff0c;每行一个正整数n。 输出格式#xff1a; 每行输出…题目描述 a[1]a[2]a[3]1 a[x]a[x-3]a[x-1] (x3) 求a数列的第n项对100000000710^97取余的值。 输入输出格式 输入格式 第一行一个整数T表示询问个数。 以下T行每行一个正整数n。 输出格式 每行输出一个非负整数表示答案。 输入输出样例 输入样例#1 3
6
8
10输出样例#1 4
9
19说明 对于30%的数据 n100 对于60%的数据 n2*10^7 对于100%的数据 T100n2*10^9 题解 其实这篇本来想写日记的但是老师突然来到了我的身边我就迅速把这道刚做完的题粘到了这里。 有始有终就写吧。 谁可以告诉我为什么我的暴力没有分 众人OS你错了呗。 #include cstdio
#include cstring
using namespace std;typedef long long LL;
const int mod1e97;
int T, n;
LL tmp[3][3]{{0,0,1},{1,0,0},{0,1,1}};struct Matrix33{LL mat[3][3];Matrix33 operator *(Matrix33 b){Matrix33 m;for (int i0; i3; i) for (int j0; j3; j){m.mat[i][j]0;for (int k0; k3; 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 ansunit;while (n){if (n1) ansans*plus;plusplus*plus;n1;}return ans;
}int main(){unit.mat[0][0]unit.mat[1][1]unit.mat[2][2]1;beg.mat[0][0]beg.mat[0][1]beg.mat[0][2]1;scanf(%d, T);for (int tt0; ttT; tt){scanf(%d, n);if (n4) printf(1\n);else printf(%lld\n, (beg*get_mat(n-3)).mat[0][2]);}return 0;
} AC 一世安宁转载于:https://www.cnblogs.com/GTBA/p/9441336.html
