传送门
题意：
有一个长度为nnn的数列的未知数列，数列的每一个数的值都在区间[l,r][l,r][l,r]的范围内。现在问你能够构成多少个这样的数组，使得数组内的所有数的和能够被333整除。
题目分析：
在这个题中，我们不能纠结在具体的数值的变化，我们需要关注数量的变化。
首先，涉及到这类整除性的问题，我们需要将它转化成余数的问题。那么我们可以发现，这些数的余数只会在[0,2][0,2][0,2]的范围之间变化，因此我们只需分别考虑这三种情况。
我们考虑这样一个问题。如果一个数xxx能够被333整除，则我们设x=3kx=3kx=3k。而因为l≤x≤rl\le x \le rl≤x≤r，则我们有l3≤k≤r3\frac{l}{3}\le k\le \frac{r}{3}3l≤k≤3r。则易得，能被333整除的数的个数为：r3−l3\frac{r}{3}-\frac{l}{3}3r−3l。
同理有，模333余111的个数为：r−13−l−13\frac{r-1}{3}-\frac{l-1}{3}3r−1−3l−1
模333余222的个数为：r−23−l−23\frac{r-2}{3}-\frac{l-2}{3}3r−2−3l−2
得到个数之后，我们就可以用dpdpdp对答案进行转移。
我们设dp[i][j]dp[i][j]dp[i][j]为数列的前iii个数字被取了后，余数为jjj的方案数，cnt[i]cnt[i]cnt[i]为在区间[l,r][l,r][l,r]中，模333余iii的个数。
则我们容易发现，当前的状态，是由前一个状态分别加上余000，余111，余222的方案数转移过来的，即有状态转移方程：dp[i][j+k]+=dp[i−1][j]∗cnt[k]dp[i][j+k]+=dp[i-1][j]*cnt[k]dp[i][j+k]+=dp[i−1][j]∗cnt[k]。
因此我们可以用O(n)\mathcal{O}(n)O(n)的时间复杂度进行转移，最终的答案即为dp[n][0]dp[n][0]dp[n][0]
#include <bits/stdc++.h>
#define maxn 200005using namespace std;
typedef long long ll;
ll dp[maxn][3];
const int mod=1e9+7;
int main()
{int n,l,r;scanf("%d%d%d",&n,&l,&r);l--;dp[0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<3;j++){ll w=(r-j+3)/3-(l-j+3)/3;for(int k=0;k<3;k++){dp[i+1][(k+j)%3]=(dp[i+1][(k+j)%3]+dp[i][k]*w)%mod;}}}cout<<dp[n][0]<<endl;return 0;
}