### HZC's blog

By HZC, 9 months ago, ,

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

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

• 0