Codeforces 1105C Ayoub and Lost Array|DP

题目链接

题意：从$l​$到$r​$中选$n​$个数，允许相同。要使最终这$n​$个数的和是$3​$的倍数，求有多少个方案，答案$mod​$ $10^9+7​$。(若没有方案，输出$0​$)

题解：

首先$1\le l\le r\le 10^9$，显然不能从$l$,$r$下手。我们可以从$3$思考一下，显然，求$n$个数的和为$3$的倍数，就是余数加起来为$3$的倍数。所以，对于一个方案，把里面的某一个数换成余数与其相同的数，方案仍然成立。

我们容易想到DP，设$f[i][j]​$为到第$i​$个数时，前$i​$个数的和$mod​$ $3​$为$j​$的方案数。转移这里就不说了，具体见代码。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,l,r;
long long mod0,mod1,mod2,f[200100][3];//记得开long long
int main()
{
    cin>>n>>l>>r;
    mod0=r/3-l/3;
    mod1=mod0;
    mod2=mod0;
    if (l%3==0) mod0++;
    if (l%3==2) mod1--;
    if (r%3==1) mod1++;
    if (r%3==2) mod1++,mod2++;//求出l到r中模3余数为0、1、2的数
    f[0][0]=1;
    for (int i=1;i<=n;i++)
    {
        f[i][0]=(f[i-1][0]*mod0)%mod+(f[i-1][1]*mod2)%mod+(f[i-1][2]*mod1)%mod;
        f[i][0]%=mod;
        f[i][1]=(f[i-1][1]*mod0)%mod+(f[i-1][2]*mod2)%mod+(f[i-1][0]*mod1)%mod;
        f[i][1]%=mod;
        f[i][2]=(f[i-1][0]*mod2)%mod+(f[i-1][1]*mod1)%mod+(f[i-1][2]*mod0)%mod;
        f[i][2]%=mod;
    }//DP，注意取模
    cout<<f[n][0]<<endl;
    return 0;
}

本文同步发布于本人luogu blog。