好玩题。

以下称“先手”为第一次拿石子的人，“获胜”指拿到最后一个石子（与原题定义不同），“失败”指未获胜。

---

由齐肯多夫定理可知，任何正整数都可以唯一地表示为若干个不连续的斐波那契数之和。

那么如果 $n=F_i$，则先手必须全取走，否则必败。

:::info[证明]

这是因为 $F_i = F_{i-1} + F_{i-2}$，将问题按“第一次取走个数”和 $F_{i-2}$ 的大小划分。

1. 第一次取走个数达到 $F_{i-2}$

那么 $F_{i-1} < 2F_{i-2}$，所以后手可以直接全取走。

2. 第一次取走个数不到 $F_{i-2}$

考虑数学归纳法。

step 1：当 $n \le 2$ 时，先手取不了 $< F_{i-2}$ 个，所以后手赢；

step 2：当 $n>2$ 时，如果先手取了 $x<F_{i-2}$ 个，那么考虑前 $F_{i-2}$ 个石子的子问题当中，后手获胜。

此时考虑剩余的 $F_{i-1}$ 个依旧是先手一方先手。而如果这 $F_{i-1}$ 个中，先手取了 $\ge F_{i-3}$ 个依旧是输完了 $^1$，所以我们考虑 $F_{i-1}$ 取 $<F_{i-3}$ 个的 case。然后你会发现这不就跳到 step 1 了吗，证明完毕。

$^1$ 处注：由于后手上一步不超过 $\dfrac{2}{3} F_{i-2}$，又有 $\dfrac{4}{3}F_{i-2}<F_{i-1}(i>3)$，则取不到全部 $F_{i-1}$，故不存在胜的策略。

:::

---

而齐肯多夫表示法有什么性质呢？我们发现 $$2 \times F_{k-2} < F_k$$。

这就是说，如果用齐肯多夫表示法 $n = F_{p_1}+F_{p_2}+\cdots+F_{p_k}(p_1<p_2<\cdots<p_k)$，那么先手如果恰好取走 $F_{p_k}$ 就一定赢了。这是因为，$2 \times F_{p_k}<F_{p_{k-1}}$，所以 $k-1$ 那一堆石子的最后一块一定还是先手拿到的。递推一下发现第 $1$ 堆是同理的。

那为什么这样最优呢？我们考虑第一次如果没有拿满 $F_{p_k}$，那么 $F_{p_k}$ 的子问题后手胜利，而先手就又拿不满 $F_{p_{k-1}}$ 了，一步输步步输，先手输完了。

以上：

当 $n=F_i$ 成立时，先手必须全取完；否则齐肯多夫表示法 $n=F_{p_1}+\cdots+F_{p_k}(p_1<\cdots<p_k)$，先手必须恰好取 $F_{p_k}$ 个。

到这里你就做完了 P6487 [COCI 2010/2011 #4] HRPA，但是这道题还有一步。

---

这个题 $T,N,k$ 还是很大。

数位 dp 首先要有一个明确的进制，但是这道题由于结论是斐波那契相关的，于是考虑 Fib-进制。其实就是问你 Fib-进制中，$1 \sim n$ 有多少个数 $x$ 满足 $\text{lowbit}(x) \le k$，也就是先手拿不完第一堆。这不就是数位 dp 板子吗/kel

$$\sum\limits_{i=1}^n [\text{lowbit}(i) \le k] = n-\sum\limits_{i=1}^n [\text{lowbit}(x) >k]$$

然后直接做啊。复杂度 $\mathcal O(T \log N)$，具体的话 $\log_{\phi}(10^{18}) \approx 88$。

一个问题是原题目中称“胜利”为拿到最后一个石子。所以代码中先 n-- 以符合定义。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int F[90],dp[90][2][2];
bool v[90];

int solve(int cur,bool up,bool lst,int k){
    if(F[cur]<=k)return 1;
    if(~dp[cur][up][lst])return dp[cur][up][lst];
    int r=solve(cur-1,up&&!v[cur],0,k);
    if(!lst&&(!up||v[cur]))r+=solve(cur-1,up,1,k);
    return dp[cur][up][lst]=r;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T,k,n;cin>>T;
    F[1]=1,F[2]=2;
    for(int i=3;i<=87;i++)
        F[i]=F[i-1]+F[i-2];
    while(T--){
        cin>>k>>n;n--;
        for(int i=87,t=n;i;i--){
            if(t>=F[i])v[i]=1,t-=F[i];
            else v[i]=0;
            dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=-1;
        }
        cout<<n+1-solve(87,1,0,k)<<'\n';
    }
}