B - 系数

这个题目证明方法暂时没有想出来，但是已经可以通过打表的方式解决掉了。

化简

首先 ， 在取模的意义下

然后我所要的第 k 项就是

那么只要求出 最后的组合数关于 3 取模的值即可。

首先有如下的打表代码 。

打表

#include<iostream>
using namespace std;

int c[1000][1000];

int main(){
    for(int i = 0 ; i <= 90 ; i ++){
        printf("%3d : ",i);
        for(int j = 0 ; j <= i ; j ++){
            if(i == j || j == 0) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % 3;
            // if(i % 2 == 0)
                // printf("%d ",c[i][j]);
            if(c[i][j] == 0) printf("- ");
            else if(c[i][j] == 1) printf("+ ");
            else if(c[i][j] == 2) printf("| ");
        }
        printf("\n");
    }
    return 0;
}

为了便于观察嘛 ， 我们把 0 打成 "-" ， 1 打成 "+" , 2 打成 "|"

得到如下的一张表

那么这个关系就很明显咯，这个题目显然是要用分形的方法来做。

找规律

我们首先可以发现，每个减号的三角形总是倒着的，而且它们开始的那一边总是 有 或是 这样的形式。并且它们的结尾恰巧就是上一条边减去 1.

由此我们就可以得到初步的规律。它们关于 3 的 k 次幂分形。

然后我们分为两块来观察

第一块 ：
第二块 ：

一、

首先看第一块，我们发现这个图形有两个三角形组成，全为减号的三角形和不全为 0 的三角形

然后这个不全为 0 的三角形又刚好是减号三角形上面那一块三角形。

因此，在这里，它的规律就是，如果遇到中间那块三角形，则返回 0 反之则返回它上面的三角形。

二、

然后再看第二块，我们发现这是由 3 种三角形组成

首先判断，全为 0 的三角形返回零

然后，我们发现两边的三角形刚好就是第一块两边的三角形，第一块两边的三角形又是上面的三角形，因此我们直接返回到上面的三角形即可。

最后，最中间的三角形和两边的三角形差不多，但有变化。

其中 + --> | ， | --> + 。
转化为数字就是 1 --> 2 , 2 --> 1。
也就是 (3 - x) % 3 的值。
0 在这个情况下也成立。

那么返回到上面的三角形。并且设置一个判断，是否改变。

好 ， 规律到这里也就找完了。

出结果。

由于题目中的答案要的是

那么我们在判断 k 的奇偶即可。

AC 代码

不知道为什么非要我打表打到100，否则就段错误。

#include<iostream>
#define ll long long
using namespace std;

int c[110][110];

int solve(ll x,ll y,bool f){ // 2 --> 1 | 1 --> 2
    if(x <= 100 && y <= 100){
        if(f) return (3 - c[x][y]) % 3;
        return c[x][y]; 
    }
    ll s = 81;
    while(s <= x) s*=3; s /= 3;
    if(x >= s && x < s * 2){
        if(y > x - s && y < s) return 0;
        else return solve(x % s,y % s,f);
    }
    else{
        if(y >= s && y < s * 2) return solve(x - s,y % s, !f);
        return solve(x - s,y % s,f);
    }

}

int main(){
    for(int i = 0 ; i <= 105 ; i ++){
        for(int j = 0 ; j <= i ; j ++ ){
            if(i == j || j == 0) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % 3;
        }
    }
    int t ; cin >> t;
    while(t--){
        ll n , k ; cin >> n >> k;
        n *= 2;
        int s = solve(n,k,0);
        if(k & 1) s = (- s + 3) % 3;
        cout << s << "\n";
    }
    return 0;
}