询问 / sosoo

_H17_ · 2026-07-24 10:11:41 · 题解

前言

被我任务计划中题创飞的概率大概是 50\% 远高于平时。

题目分析

首先直接模拟肯定不可做，你猜最终一定会变成某种特定的情况。

你推式子发现如果一次是 (a,b)\to(2b-i,2a-i)，下一次必然也是（i\ge 3 是条件）。

其实出现 (a,b)\to(a+i,b+i) 也可以，但是似乎不存在。

然后其实直接暴力变化直到出现循环情况之后矩阵快速幂就拿下了。

有题解证明了这个数据范围下最多跑 30 次（我不会证明），如果认为这是常数，时间复杂度 O(T\log n)。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr __int128 p=1e9+7;
int T,n,a,b,mul[4][4];
array<__int128,2>cur;
array<__int128,2>f(__int128 i,array<__int128,2>x){
    auto[a,b]=x;
    return{max(2*b-i,a+i),max(2*a-i,b+i)};
}
void squaremul(){
    static int tmp[4][4];
    memset(tmp,0,sizeof(tmp));
    for(int k=0;k<4;k++)
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                (tmp[i][j]+=mul[i][k]*mul[k][j])%=p;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            mul[i][j]=tmp[i][j];
    return;
}
void task(){
    mul[0][0]=0,mul[0][1]=2,mul[0][2]=0,mul[0][3]=0;
    mul[1][0]=2,mul[1][1]=0,mul[1][2]=0,mul[1][3]=0;
    mul[2][0]=-1,mul[2][1]=-1,mul[2][2]=1,mul[2][3]=0;
    mul[3][0]=0,mul[3][1]=0,mul[3][2]=1,mul[3][3]=1;
    cin>>n>>a>>b;
    cur={a,b};
    for(int i=1;i<=n;i++){
        a=cur[0],b=cur[1];
        if(i>=3&&2*b-i>=a+i&&2*a-i>=b+i){
            array<int,4>curi={a%p,b%p,i%p,1},tmp;
            int bb=n-i+1;
            while(bb){
                if(bb&1){
                    tmp={0,0,0,0};
                    for(int k=0;k<4;k++)
                        for(int j=0;j<4;j++)
                            (tmp[j]+=curi[k]*mul[k][j])%=p;
                    curi=tmp;
                }
                squaremul(),bb>>=1;
            }
            cur={curi[0],curi[1]};
            break;
        }
        else
            cur=f(i,cur);
    }
    cur[0]=(cur[0]%p+p)%p,
    cur[1]=(cur[1]%p+p)%p;
    println("{} {}",cur[0],cur[1]);
    return;
}
string program(){
    for(cin>>T;T;T--)
        task();
    return"H17";
}
string H17=program();
signed main(){
    return 0;
}