HZC's blog

By HZC, 9 months ago, In English,

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写法,还有大佬用爆搜做:传送门

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it