题目大意：

　　一个长度为$n$的数组，其和能被$3$整除，且每一个数字满足$a_{i}\in [l,r]$，问有多少种可以满足上述三个条件的数组

分析：

　　$dp$。$dp[i][j]=$前$i$个数构成余数为$j$的方案数，然后通过这个$dp$的定义，可以推出递推方程

　　　　　　　　　　　　$dp[i][j]=\sum_{j=0}^{2}\sum_{k=0}^{2}dp[i][ (j+k)\%3 ] \times n[(3-k)\%3]$

其中$n[(3-k)\%3]$为满足数字$a_{i}\in [l,r]$余数为$k$的个数，而$n[k]$的求法也很简单。

　　以余数为$1$为例，假设$a_{i}=3\cdot m +1$,容易得到$l\leq 3\cdot m+1\leq r$，

　　　　　　　　　　即$\frac{l-1}{3}\leq k\leq \frac{r-1}{3}$，

而其间的个数有为$\lfloor  \frac{l-2}{3} \rfloor -\lfloor  \frac{r-1}{3} \rfloor$，但是由于$-2$可能会出现$-1$或者$-2$，会影响到范围，所以我们两边都加上$3$，于是就变成了 $\lfloor  \frac{l+1}{3} \rfloor -\lfloor  \frac{r+2}{3} \rfloor$，另外两种情况计算同上。

code:

 

#define debug#include 
     
      using namespace std;typedef long long ll;const int maxn = 1e7;const int MAXN = 1e3 + 10;const ll INF = 0x3f3f3f3f;const ll inf = 0x7fffff;const ll mod = 1e9 + 7;const int MOD = 10007;ll dp[maxn][3];void solve() {	ll n,l,r;	cin>>n>>l>>r;	ll nn[3]= {r/3-(l-1)/3,(r+2)/3-(l+1)/3,(r+1)/3-(l)/3};	dp[0][0]=1;	for(int i=1; i
      
       >T;	while(T--)		solve();	return 0;}