USACO 2021 Feb T3 Count the Cows G

green_orange · 2021-03-07 14:39:48 · 题解

USACO 2021 Feb T3 Count the Cows G

分析

首先转化题意，分析题中所给出的 \lfloor\frac{x}{3^k}\rfloor 和 \lfloor\frac{y}{3^k}\rfloor：

对于向下取整，我们所拥有的技巧相对较少，我们不妨将其写成如下形式：

其中 r_0, r_1 \le 3^k - 1，那么我们所分析的条件可转化为 a, b 之间的关系。

接下来分析 a, b 的性质

我们观察到对于不同的 k 值, a, b 的系数始终是 3 的次幂，而题目中所给的关系中出现了对于 3 的余数，这启发我们将 a,b 中再提出一个 3 来。那么有

题目中的关系可转化为 q_x \equiv q_y \pmod{2}。

我们发掘出了对于单一的 k 其具有的性质，考虑对于所有的 k

展开上式

我们发现有大量 3 的次幂，这启发我们尝试将 r 也写成 3 的次幂相加的形式

题目所给关系转化为 \forall k, a_k \equiv b_k \pmod{2}。

根据我们的经验，我们发现上式中的形式就是 x, y 的三进制，要求转化为 x, y 三进制下每一位关于 2 同余。

这个结论对我们来说大有脾益，那么，我们就是求有多少的 d \in [d, d_0] 满足 x_0 + d 与 y_0 + d 三进制每一位下关于 2 同余。我们可以很容易联想到数位DP, 设状态为当前DP到多少位，x_0 + d，y_0 + d 的更低位在做加法时有没有进位 ，由高位向低位DP即可，时间复杂度 O(q\log x)。

实现

#include <bits/stdc++.h>
using namespace std;
const static int mlg = 40;
#define int long long
int f[mlg][2][2][2];
bool vis[mlg][2][2][2];
int Ab[mlg], Bb[mlg], lb[mlg];
bool check(int a, int b) {
    if (a < 0 || b < 0 || a > 2 || b > 2)
      return false;
  else if ((a & 1) == (b & 1))
    return true;
  else
    return false;
}
typedef long long inte;
inline int dfs(int p/*第几位*/, bool a/*x 是否进位*/, bool b/*y 是否进位*/, bool lim/*d 是否被顶满*/) {
    if (p < 0)
      return (a == 0) && (b == 0);
    if (vis[p][a][b][lim])
      return f[p][a][b][lim];
  vis[p][a][b][lim] = true;
    inte ans = 0;
    for (int v = 0; v <= (lim ? lb[p] : 2); ++v) {
        for (int ak = 0; ak <= 1; ++ak) {
            for (int bk = 0; bk <= 1; ++bk) {
                if (check(Ab[p] - 3 * a + v + ak, Bb[p] - 3 * b + v + bk)) {
                    ans += dfs(p - 1, ak, bk, lim & (v == lb[p]));
                }
            }
        }
    }
    return f[p][a][b][lim] = ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int Q;
    cin >> Q;
    while (Q--) {
        inte x, y, d;
        cin >> d >> x >> y;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < mlg; ++i) {
            Ab[i] = x % 3;
            x /= 3;
            Bb[i] = y % 3;
            y /= 3;
            lb[i] = d % 3;
            d /= 3;
        }
        cout << dfs(mlg - 1, 0, 0, true) << endl;
    }
  return 0;
}