2018 Multi-University Training Contest 7 1010

题意：给出A,B,C,D,P,n，根据地推公式求出第n项

首先把这个递推公式化成矩阵公式，发现p/n项会变化，所以无法直接求矩阵，但是每个p/n都有一个连续的固定值，所以可以暴力出所有p/n的值，再化成矩阵求快速幂。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
ll A, B, C, D, P, n;
struct node
{
    ll c[3][3];
}f;
void init()
{
    f.c[0][0] = D, f.c[0][1] = C, f.c[0][2] = 1;
    f.c[1][0] = 1, f.c[1][1] = f.c[1][2] = 0;
    f.c[2][0] = f.c[2][1] = 0, f.c[2][2] = 1;
}
node work(node a,node b)
{
    node x = { 0 };
    for (int i = 0;i < 3;i++)
    {
        for (int j = 0;j < 3;j++)
        {
            for (int k = 0;k < 3;k++)
            {
                x.c[i][j] += (a.c[i][k] * b.c[k][j] % mod);
                x.c[i][j] %= mod;
            }
        }
    }
    return x;
}
node ksm(node y,int b)
{
    init();
    node x = f;b--;
    while (b)
    {
        if (b % 2 == 1) x = work(x, f);
        f = work(f, f);
        b /= 2;
    }
    y = work(x, y);
    return y;
}
int main()
{
    int i, j, k, sum, t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
        if (n == 1)
        {
            printf("%lld\n",A);
            continue;
        }
        if (n == 2)
        {
            printf("%lld\n", B);
            continue;
        }
        init();
        node y;
        y.c[0][0] = B, y.c[1][0] = A;
        y.c[0][1] = y.c[0][2] = 0;
        y.c[1][1] = y.c[1][2] = 0;
        y.c[2][1] = y.c[2][2] = 0;
        int now = 3;
        while(now<=n)
        {
            y.c[2][0] = P / now;
            int l , r , len, next = P + 1;
            if (now > P) len = n - now + 1, now = n + 1;
            else
            {
                l = now + 1, r = P;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if ((int)P / mid < (int)P / now)
                        r = mid - 1, next = mid;
                    else l = mid + 1;
                }
                if (next - 1 >= n) len = n - now + 1, now = n + 1;
                else len = next - now, now = next;
            }
            y = ksm(y, len);
        }
        printf("%lld\n", y.c[0][0] % mod);
    }
    return 0;
}