游客 注册 | 登录
中文 | En

3496 - 国王的奖励

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

 这里的国王不是人类的国王哦，是蚂蚁的国王（就是蚁后啦），国王非常讨厌过来领奖还排在那么后面的蚂蚁，于是，国王规定，第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>

题目输入

 测试包含多组测试数据 

<span style="font-size:16px;font-family:宋体;">第一行为一个整数</span><span style="font-size:16px;">n,1&lt;=n&lt;=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&lt;=x,y,z,a,b,c&lt;=10</span>

题目输出

 对于每组测试数据输出一行，为第一只蚂蚁可以领到的奖励

输入/输出样例

输入格式

4
1 1 1 2 2 2

输出格式

6

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;
}
请先登陆