这道题是一道dp题，给出数组的个数n，上下边界l和r（包括l，r），要求满足所有数组中元素之和满足被3整除的情况有多少种，
我们可以知道l到r中被3整除的数有mod0个，被3整除余1的有mod1个，被3整除余2的有mod2个。
dp[i][j]表示数组中前i个数的和被3整除余j的个数，我们要求的就是dp[n][0];
dp[i][0]=dp[i][0]*mod0+dp[i][1]*mod2+dp[i][2]*mod1,依次类推
1 #include<iostream> 2 #include<string.h> 3 #include<string> 4 #include<sstream> 5 #include<vector> 6 #include<deque> 7 #include<map> 8 #include<algorithm> 9 #include<iomanip> 10 #include<math.h> 11 #include<set> 12 using namespace std; 13 14 int mod = 1000000007; 15 typedef long long ll; 16 typedef unsigned long long ull; 17 ll dp[200005][3]; 18 19 int main() 20 { 21 ll n,l,r; 22 while (cin >> n >> l >> r) 23 { 24 25 ll mod0 = r/3-l/3; 26 if (l % 3 == 0) 27 mod0+=1; 28 ll mod1 = (r + 2) / 3 - (l + 2) / 3; 29 if ((l + 2) % 3 == 0) 30 mod1 += 1; 31 ll mod2 = r-l+1-mod0-mod1; 32 memset(dp, 0, sizeof(0)); 33 dp[1][0] = mod0; 34 dp[1][1] = mod1; 35 dp[1][2] = mod2; 36 for (int i = 2; i <= n; i++) 37 { 38 dp[i][0] = (dp[i - 1][0] * mod0 + dp[i - 1][1] * mod2 + dp[i - 1][2] * mod1)%mod; 39 dp[i][1] = (dp[i - 1][0] * mod1 + dp[i - 1][1] * mod0 + dp[i - 1][2] * mod2) % mod; 40 dp[i][2]= (dp[i - 1][0] * mod2 + dp[i - 1][1] * mod1 + dp[i - 1][2] * mod0) % mod; 41 } 42 cout << dp[n][0] % mod << endl; 43 } 44 return 0; 45 }
原文：https://www.cnblogs.com/QingFengDaHui/p/10485380.html