get_count

#include<bits/stdc++.h>
using namespace std;
int N, L, R;
const int MOD = 1e9 + 7;
int dp[2][3];
int countt[3];
int prefix_sum[3];
int get_count(long long x, int r) {
	if (x < r) 
		return 0;
	return (x - r) / 3 + 1;
}

int main() {
	scanf("%d%d%d", &N, &L, &R);
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[0][2] = 0;
	

	for (int r = 0; r < 3; r++) {
		countt[r] = get_count(R, r) - get_count(L-1, r);
	}
	
	int current = 0;
	int next = 1;
	
	for (int i = 1; i <= N; i++) {
		dp[next][0] = dp[next][1] = dp[next][2] = 0;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				int new_mod = (j + k) % 3;
				dp[next][new_mod] = (dp[next][new_mod] + (long long)dp[current][j] * countt[k]) % MOD;
			}
		}
		current = next;
		next = 1 - next;
	}
	
	printf("%d\n", dp[current][0]);
	return 0;
}

求一个区间内模N的各个数字的个数，最快的办法怎么做？
——用公式计算。
当然可以！让我们来详细分析一下 get_count 函数的作用。

函数定义

int get_count(long long x, int r) {
    if (x < r) 
        return 0;
    return (x - r) / 3 + 1;
}

函数的作用

get_count 函数的作用是计算在范围 ([r, x]) 内，有多少个数除以3的余数等于 (r)。

参数解释

• x：范围的上限。
• r：目标余数，即我们想要计算的数除以3的余数。

返回值

函数返回在范围 ([r, x]) 内，有多少个数除以3的余数等于 (r)。

详细分析

1. 边界条件：

   • 如果 x < r，那么在范围 ([r, x]) 内没有数可以满足条件，因此返回0。

2. 计算公式：

   • 对于范围 ([r, x])，我们需要找出所有满足 (n \mod 3 = r) 的数 (n)。
   • 这些数可以表示为 (n = 3k + r)，其中 (k) 是非负整数。
   • 最小的 (n) 是 (r)，最大的 (n) 是 (x)。
   • 因此，我们需要找出所有满足 (r \leq 3k + r \leq x) 的 (k)。

3. 推导公式：

   • 从 (r \leq 3k + r)，我们得到 (k \geq 0)。
   • 从 (3k + r \leq x)，我们得到 (k \leq \frac{x - r}{3})。
   • 因此，(k) 的取值范围是从0到 (\left\lfloor \frac{x - r}{3} \right\rfloor)。

4. 计算数量：

   • 满足条件的 (k) 的数量是 (\left\lfloor \frac{x - r}{3} \right\rfloor + 1)。

示例

假设 (x = 10)，(r = 1)，我们来计算在范围 ([1, 10]) 内，有多少个数除以3的余数等于1。

• 最小的数是 (1)（即 (3 \times 0 + 1)）。
• 最大的数是 (7)（即 (3 \times 2 + 1)）。
• 满足条件的数是 (1, 4, 7)，共有3个。

使用公式：
[
\left\lfloor \frac{10 - 1}{3} \right\rfloor + 1 = \left\lfloor \frac{9}{3} \right\rfloor + 1 = 3 + 1 = 3
]

代码中的应用

在代码中，get_count 函数用于计算每个模3的结果对应的成色值数量。具体来说：

• countt[r] = get_count(R, r) - get_count(L-1, r);
  • get_count(R, r) 计算在范围 ([0, R]) 内，有多少个数除以3的余数等于 (r)。
  • get_count(L-1, r) 计算在范围 ([0, L-1]) 内，有多少个数除以3的余数等于 (r)。
  • 两者的差值就是范围 ([L, R]) 内，有多少个数除以3的余数等于 (r)。

总结

get_count 函数通过简单的数学推导，快速计算在某个范围内，有多少个数除以3的余数等于某个特定值。这在动态规划的状态转移中非常有用，可以显著减少计算量。