自动搬运

查看原文

来自洛谷，原作者为

	green_orange Coding...

搬运于2025-08-24 22:29:40，当前版本为作者最后更新于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;
}