1008: QAQ的矩阵价值 [思维]
时间限制: 1 Sec 内存限制: 128 MB提交: 37 解决: 12
题目描述
QAQ有一个这样的矩阵序列（假定我们用二维数组a[][]
来记录该序列）：
n = 1 n = 2 n = 3 n = 4 n = 5 n = ...
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5
1 1 1 2 2 1 2 3 3 1 2 3 4 4
1 1 1 1 2 2 2 1 2 3 3 3 ......
1 1 1 1 1 2 2 2 2
1 1 1 1 1
QAQ定义矩阵元素a[i][j]
的价值 = a[i][j]∗10n−j
。
QAQ定义一个矩阵的价值为矩阵中所有元素价值之和。
为了增加难度，QAQ将该矩阵序列变成两个不同的矩阵序列：（如n=5时）
一 二
1 0 0 0 0 0 0 0 0 5
1 2 0 0 0 0 0 0 4 4
1 2 3 0 0 0 0 3 3 3
1 2 2 2 0 0 2 2 2 2
1 1 1 1 1 1 1 1 1 1对于上面给出的三个矩阵，请你分别求出它们的价值ans0，ans1，ans2
。
注：矩阵的行列下标均是1−n
。
输入
第一行输入一个整数T
，代表有T组测试数据。
每组数据输入一个整数n，代表矩阵序列是n∗n的。
注：1<=T<=10000，1<=n<=100000
。
输出
对每组数据，输出三个整数ans0，ans1，ans2
，中间用空格隔开，最后一个数后面没有空格。
由于结果很大，请对(109+7)
取余。
样例输入
5
1
3
5
100
5000
样例输出
1 1 1 356 331 136 60355 57631 13715 311833527 324678596 120264545 770817050 915988694 926824673
#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const LL mod = 1000000000 + 7; const LL maxn = 100011; int main() { LL ans0[maxn],ans1[maxn],ans2[maxn]; LL one[maxn],add[maxn]; LL sum = 1,ss = 1; ans0[1] = 1, ans1[1] = 1, ans2[1] = 1; one[1] = 1; add[1] = 1; for(int i = 2; i <= maxn; i++) one[i] = (one[i - 1]*10 + 1)%mod; for(int i = 2; i <= maxn; i++) { int a; if(i % 2 == 0) a = i /2; else a = i / 2 + 1; add[i] = (add[i - 1]*10)%mod + one[a]%mod; sum = (sum + i)%mod; ss = (ss*10%mod + i)%mod; ans0[i] = (ans0[i - 1]*10%mod + sum + ss - i)%mod; ans1[i] = (ans1[i - 1]*10%mod + add[i])%mod; ans2[i] = (ans2[i - 1]*10%mod + sum)%mod; } int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%lld %lld %lld\n",ans0[n],ans1[n],ans2[n]); } return 0; }
