每日一题：数数组

题目

构造一个长度为 $n$ 的序列，每个数字大小必须满足 $l <= a[i] <= r$，且和被 3 整除，问有多少种方法？

Solution

$dp[i][j]$ 表示长度为 $i$，余数为 $j$ 的构造数量。$a,b,c$ 表示区间内余数为 $0,1,2$ 的数的数量。

转移方程：

$dp[i][0] = a dp[i - 1][0] + b dp[i - 1][2] + c dp[i - 1][1]$;
$dp[i][1] = (a dp[i - 1][1] + b dp[i - 1][0] + c dp[i - 1][2]$;
$dp[i][2] = (a dp[i - 1][2] + b dp[i - 1][1] + c * dp[i - 1][0]$;

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, l, r, dp[200005][3], a, b, c;
const ll mod = 1e9 + 7;

int main() {
  cin >> n >> l >> r;
  while (l % 3 != 0) {
    int x = l % 3;
    if (x == 1)
      b++;
    else if (x == 2)
      c++;
    l++;
  }
  while (r % 3 != 0) {
    int x = r % 3;
    if (x == 2)
      c++;
    else if (x == 1)
      b++;
    r--;
  }
  int p = (r - l) / 3;
  a += p;
  b += p;
  c += p;
  a++;
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = (a * dp[i - 1][0] + b * dp[i - 1][2] + c * dp[i - 1][1]) % mod;
    dp[i][1] = (a * dp[i - 1][1] + b * dp[i - 1][0] + c * dp[i - 1][2]) % mod;
    dp[i][2] = (a * dp[i - 1][2] + b * dp[i - 1][1] + c * dp[i - 1][0]) % mod;
  }
  cout << dp[n][0] << endl;
  return 0;
}