British: Title Link：https://codeforces.com/contest/1105/problem/C From the title , what we need is sequence sum divided by 3 ，no matter what mess it's stuffed with。Think about "dp". The shift formula is obvious：

f[i][j]=∑(k=l) (r) f[i-1][(j-k)%3];

Complexity of time is O(n(r-l)）, Complexity of memory is O(n). We can find that n is quivalent to n%3，The shift formula turn to：

f[i][j]=∑(k=0) (2) f[i-1][(j-k)%3]*r[k];

Complexity of time is O(n）, Complexity of memory is O(1).

The code: #include<cstdio> #define Rint register int #define ll long long const ll maxn=200010; const ll mod=1000000007; ll n,l,r,f[maxn][3],a[3]; int main(){ scanf("%I64d%I64d%I64d",&n,&l,&r); a[0]=r/3-(l-1)/3,a[1]=(r+2)/3-(l+1)/3,a[2]=(r+1)/3-l/3; f[0][0]=(long long)1; for(Rint i=1;i<=n;i++)for(Rint j=0;j<3;j++)for(int k=0;k<3;k++) f[i][(j+k)%3]=(f[i][(j+k)%3]+f[i-1][j]*a[k]%mod)%mod; printf("%I64d\n",f[n][0]); }

This is a more routine way of writing, there are also some coding masters using explosive search to do:

Magical Portal

Chinese

题目链接：https://codeforces.com/contest/1105/problem/C 由题意，我们所需要的是序列总和被3整除，不管它里面塞了什么乱七八糟的东西。考虑dp。

转移显而易见：

f[i][j]=∑(k=l) (r) f[i-1][(j-k)%3];

时间O(n(r-l)），空间O(n)，看看时间好像不太够

可以发现n与n%3是等价的，转移变成： f[i][j]=∑(k=0) (2) f[i-1][(j-k)%3]*r[k]; 时间O(n)，加上滚动数组后空间O(1)

代码扔上： #include<cstdio> #define Rint register int #define ll long long const ll maxn=200010; const ll mod=1000000007; ll n,l,r,f[maxn][3],a[3]; int main(){ scanf("%I64d%I64d%I64d",&n,&l,&r); a[0]=r/3-(l-1)/3,a[1]=(r+2)/3-(l+1)/3,a[2]=(r+1)/3-l/3; f[0][0]=(long long)1; for(Rint i=1;i<=n;i++)for(Rint j=0;j<3;j++)for(int k=0;k<3;k++) f[i][(j+k)%3]=(f[i][(j+k)%3]+f[i-1][j]*a[k]%mod)%mod; printf("%I64d\n",f[n][0]); }

这是比较套路的dp写法，还有大佬用爆搜做：传送门