题目

Description

Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help.

Input

The first line contains an integer $N$ , indicting that there are $N$ sequences. Each of the following $N$ lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is $K$ , indicating that we want to know the $K$-th numbers of the sequence.

You can assume $0 < K \leq 10^9$ , and the other three numbers are in the range $[0, 2^{63})$ . All the numbers of the sequences are integers. And the sequences are non-decreasing.

Output

Output one line for each test case, that is, the $K$-th number module ($\%$) $200907$ .

Sample Input

2
1 2 3 5
1 2 4 5

Sample Output

5
16

题意

现在有一个由整数组成的序列，可能是等差数列，也可能是等比数列，但是只给出前 $3$ 个数，要求你求数列中第 $k$ 个数 $\% 200907$ 的结果。所给数列是一个非递减数列。

输入：首先是一个 $t$ 表示输入的实例个数，以下 $t$ 行每行代表一个实例。每行包括 $4$ 个整数，前 $3$ 个整数在 $[0, 2^{63})$ 范围内，表示数列的头 $3$ 个数，第 $4$ 个数是 $k$ 表示要求的数列中的第 $k$ 个数。其中 $0 < k \leq 10^9$ 。

输出：输出数列中第 $k$ 个数 $\%200907$ 的结果。

分析

假设读入的前 $3$ 个数分别为 $a_1,a_2,a_3$ .

如果 $a_2-a_1 = a_3-a_2$ 那么数列等差，公差为 $d=a_2-a_1$.所求的第 $k$ 个数为 $a_k = a_1+d*(k-1)$ .所求为 $a_k \% mod$ .否则数列为等比数列，公比为 $p=a_2/a_1$ 且公比必定为整数（可证），所求的第 $k$ 个数为 $a_k = a_1(p^{k-1})$ 。所求为 $a_k \% mod$ 。需要用到快速幂算法。

特殊情况，一个非递减数列如果既是等差又是等比数列，那么它一定是有一系列相同的数组成的。或者说如果数列的前 $2$ 个数相等，那么整个数列都相等。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod=200907;
ll quick_mod(ll a,ll n,int mod)
{
    ll t=1;
    for(;n;n>>=1,a=(a*a%mod))
        if(n&1)
            t=(t*a%mod);
    return t;
}
int main()
{
    int t;
    cin>>t;
    double a,b,c;
    ll n;
    while(t--)
    {
        cin>>a>>b>>c>>n;
        if(a+c==2*b)
        {
            ll a1=a;
            ll d=(b-a);
            ll ans=(a1%mod+((n-1)%mod)*(d%mod))%mod;
            printf("%lld\n",ans);
        }
        else
        {
            ll a1=a;
            ll t1=a1%mod;
            double q1=b/a;
            ll q2=q1;
            ll q=q2%mod;
            ll tmp=quick_mod(q,n-1,mod);
            ll ans=(t1*tmp)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}