3496 - 国王的奖励
这里的国王不是人类的国王哦，是蚂蚁的国王（就是蚁后啦），国王非常讨厌过来领奖还排在那么后面的蚂蚁，于是，国王规定，第i个人获得的奖励为第i+1个人的a倍，第i+2个人的b倍，第i+3个人的c倍的总和，现在我给出最后三个人的奖励，求第一只蚂蚁能获得的奖励是多少?
<span style="font-size:16px;font-family:宋体;">由于数据可能会非常大，我们在这里取对</span><span style="font-size:16px;">1000000007</span><span style="font-size:16px;font-family:宋体;">取模后的值</span><span></span>
Input
测试包含多组测试数据
<span style="font-size:16px;font-family:宋体;">第一行为一个整数</span><span style="font-size:16px;">n,1<=n<=10^18</span>
<span style="font-size:16px;font-family:宋体;">第二行为</span><span style="font-size:16px;">6</span><span style="font-size:16px;font-family:宋体;">个正整数</span><span></span>
<span style="font-size:16px;font-family:宋体;">为</span><span style="font-size:16px;">x,y,z,a,b,c</span>
<span style="font-size:16px;font-family:宋体;">每行的</span><span style="font-size:16px;">x</span><span style="font-size:16px;font-family:宋体;">为第</span><span style="font-size:16px;">n-2</span><span style="font-size:16px;font-family:宋体;">个人的奖励，</span><span style="font-size:16px;">y</span><span style="font-size:16px;font-family:宋体;">为第</span><span style="font-size:16px;">n-1</span><span style="font-size:16px;font-family:宋体;">个人的奖励，</span><span style="font-size:16px;">z</span><span style="font-size:16px;font-family:宋体;">为第</span><span style="font-size:16px;">n</span><span style="font-size:16px;font-family:宋体;">个人的奖励</span><span></span>
<span style="font-size:16px;font-family:宋体;">其中</span><span style="font-size:16px;">a,b,c</span><span style="font-size:16px;font-family:宋体;">的含义如题</span><span></span>
<span style="font-size:16px;">1<=x,y,z,a,b,c<=10</span>
Output
对于每组测试数据输出一行，为第一只蚂蚁可以领到的奖励
Examples
Input
4 1 1 1 2 2 2
Output
6
Hint
作者：李雪峰
Solution C++
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; #define maxn 1000000007 ll x,y,z,aa,b,c; mat mul(mat &a,mat &b) { mat c(a.size(),vec(b[0].size())); for (int i=0;i<a.size();i++){ for (int k=0;k<b.size();k++){ for (int j=0;j<b[0].size();j++){ c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%maxn)%maxn; } } } return c; } mat pow(mat a,ll n) { mat b(a.size(),vec(a.size())); for (int i=0;i<a.size();i++){ b[i][i]=1; } while(n>0){ if (n&1) b=mul(b,a); a=mul(a,a); n>>=1; } return b; } ll solve(ll n) { mat a(3,vec(3)); //指定横纵坐标的大小 a[0][0]=aa;a[0][1]=b;a[0][2]=c; a[1][0]=1;a[1][1]=0;a[1][2]=0; a[2][0]=0;a[2][1]=1;a[2][2]=0; a=pow(a,n); return ( (a[0][0]*x)%maxn + (a[0][1]*y)%maxn + (a[0][2]*z)%maxn )%maxn; } int main() { ll n; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scanf("%lld",&n)){ scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&z,&aa,&b,&c); if (n==3){ printf("%d\n",x); return 0; } if (n==2){ printf("%d\n",y); return 0; } if (n==1){ printf("%d\n",z); return 0; } printf("%lld\n",solve(n-3)); } return 0; }
Hint
作者：李雪峰