这道题是一道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 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include