Codeforces 1105C Ayoub and Lost Array (计数DP)

<题目链接>

题目大意：

有一个长度为 n 的数列的未知数列，数列的每一个数的值都在区间 [l,r]  的范围内。现在问你能够构成多少个这样的数组，使得数组内的所有数的和能够被 3 整除。

解题分析：

类似于这种数据量大的计数问题，要不就是数学推公式，要不就是dp。     

根据所有数之和能被3整除的性质，我们将所有数用%3的余数表示，推出状态转移方程：$$ dp[i][j+k]=dp[i-1][j]*num[k]  $$

$dp[i][j]$表示：前$i$项之和余$j$的方案数。

这篇博客讲解的比较详细  >>>

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

typedef long long ll;
#define N int(2e5+7)
const int mod = 1e9+7;
ll dp[N][3];

int main(){
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    int num0,num1,num2;     //得到余数分别为0,1,2的数的个数 
    num0=r/3-(l-1)/3; 
    num1=(r-1+3)/3-(l-2+3)/3;
    num2=r-l+1-num0-num1;
    dp[1][0]=num0;      //初始化dp第一项 
    dp[1][1]=num1;
    dp[1][2]=num2;
    for(int i=2;i<=n;i++){
        dp[i][0]=((dp[i-1][0]*num0)%mod+(dp[i-1][2]*num1)%mod+(dp[i-1][1]*num2)%mod)%mod;
        dp[i][1]=((dp[i-1][1]*num0)%mod+(dp[i-1][0]*num1)%mod+(dp[i-1][2]*num2)%mod)%mod;
        dp[i][2]=((dp[i-1][2]*num0)%mod+(dp[i-1][1]*num1)%mod+(dp[i-1][0]*num2)%mod)%mod;
    }
    printf("%d
",dp[n][0]);
}

2019-02-22