文章图片
Codeforces Round #533 (Div. 2)
分析：用dp做，从一位开始递推，取余0，取余1，取余2，互相组合。然后逐渐到n。
#include
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll dp[200000+5][5];
int main()
{
ll n,l,r;
while(cin>>n>>l>>r)
{
ll a,b,c;
a=r/3-(l-1)/3;
//l，r之间取余3mod0的
b=(r+2)/3-(l+1)/3;
//l，r之间取余3mod1的
c=(r+1)/3-l/3;
//l，r之间取余3mod2的
dp[1][0]=a;
dp[1][1]=b;
dp[1][2]=c;
for(int i=2;
i<=n;
i++)
{
dp[i][0]=(dp[i-1][0]*a%mod+dp[i-1][1]*c%mod+dp[i-1][2]*b%mod)%mod;
前i的几个数取余为0的数量
dp[i][1]=(dp[i-1][0]*b%mod+dp[i-1][1]*a%mod+dp[i-1][2]*c%mod)%mod;
前i的几个数取余为1的数量
dp[i][2]=(dp[i-1][0]*c%mod+dp[i-1][1]*b%mod+dp[i-1][2]*a%mod)%mod;
前i的几个数取余为2的数量
}
cout< 【题目|C. Ayoub and Lost Array（思维dp）】
推荐阅读
- 【C】题目|【C语言】题集 of ⑥
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- SSL P1520 牛的RP 题目
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II