Count the Cows (USACO Gold 2021 February)

这个题的难度主要是最简单的办法是在图上生看出规律来的，如果不在图上仔细看，就需要去想那个比较绕的DP。

如果仔细画画图，就会发现从图形上可以找到递归定义的规律：

整个图型就是一个递归定义的X，大X套小X这样。

如果我们定义 $C(k,\text{diff})$ 是 $(3^k,3^k)$ 大小的图形块中， $x-y=\text{diff}$ 的对角线的值。上图对应 $k=2$ 。

则：

如果 $\text{diff} < 3^{k-1}$ ，则 $C(k,\text{diff})=3 \cdot C(k-1,\text{diff})$
如果 $\text{diff} \geq 3^{k-1}$ ，则 $C(k,diff)=C(k-1,\text{diff}-2 \cdot 3^{k-1})$

如果不是完整的从顶到底的线，则设 $k$ 为 $3^k > \max (x,y)+d$ 的最小 $k$ ，则目标线段就在此图范围内：

如果 $x < y$ ，则swap( $x$ , $y$ )
可以把从顶到底的线的结果，减去两头：也就是 $C(k,\text{diff}) - C'(k,\text{diff},\text{len}=y) - C'(k,\text{diff},\text{len}=3^k-1-(x+d))$

其中 $C'$ 是带长度的 $C$ 函数，实现见下面代码中C2()。

DP的方法可以看官方题解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
ll ans;
ll pow3[40];
 
ll C(int k, ll diff) {
    if (diff < 0) diff = -diff;
    if (k == 0) return diff == 0;
    if (diff < pow3[k-1]) {
        return 3*C(k-1, diff);
    } else {
        return C(k-1, diff - 2*pow3[k-1]);
    }
}
 
ll C2(int k, ll diff, ll len) {
    if (diff < 0) {diff = -diff; len -= diff;};
    if (len <= 0) return 0;
    if (k == 0) return diff == 0;
    if (diff < pow3[k-1])
        return len/pow3[k-1]*C(k-1,diff) + C2(k-1,diff,len%pow3[k-1]);
    else
        return len > pow3[k-1] ? C(k-1,diff-2*pow3[k-1]) : C2(k-1,diff-2*pow3[k-1], len);    
}
 
int main() {
    scanf("%d", &n);
    pow3[0] = 1;
    for (int i = 1; i <= 39; i++)
        pow3[i] = pow3[i-1]*3;
    for (int i = 0; i < n; i++) {
        map<int,int> mx, my;
        ll d, x, y;
        scanf("%lld %lld %lld", &d, &x, &y);
        if (x < y) swap(x,y);       // make sure x > y
        int k = 0;
        while (pow3[k] <= x+d) k++;
        ll diff = x-y;
        ans = C(k,diff) - C2(k,diff,y) - C2(k,diff,pow3[k]-(x+d+1));
        printf("%lld\n", ans);
    }
    return 0;
}