CF1105C Ayoub and Lost Array(dp+矩阵快速幂优化) 前言: dp思路: dp代码: 滚动数组优化dp思路: 滚动数组优化dp代码: 矩阵快速幂优化思路: 矩阵快读幂优化代码:
求([l,r])区间里取余(3=0)的数的个数,取余(3=1)的数的个数,取余(3=2)的数的个数:
cnt[0]=(r+3)/3-(l+2)/3; //%3==0
cnt[1]=(r+2)/3-(l+1)/3;//%3==1
cnt[2]=(r+1)/3-l/3;//%3==2
dp思路:
比较好想的(dp)。我们可以将取余3相等的数看成是一类,这些数对答案的贡献都是相同的。
设(dp[i][j])表示选完了前i个数并且这个数列的和取余3为(j)的方案数。((j=0,1,2))
转移也很好想=>
对于(dp[i][0])来说:选完前(i-1)个数时和为(0),那么第(i)个数只能够选取余(3)为(0)的数;
其他也类似。
dp代码:
const ll mod=1e9+7;
ll cnt[3],dp[maxn][3];
int main(){
ll n=read,l=read,r=read;
cnt[0]=(r+3)/3-(l+2)/3; //%3==0
cnt[1]=(r+2)/3-(l+1)/3;//%3==1
cnt[2]=(r+1)/3-l/3;//%3==2
dp[0][0]=1;
for(int i=1;i<=n;i++){
dp[i][0]=(dp[i-1][0]*cnt[0]%mod+dp[i-1][1]*cnt[2]%mod+dp[i-1][2]*cnt[1]%mod)%mod;
dp[i][1]=(dp[i-1][0]*cnt[1]%mod+dp[i-1][1]*cnt[0]%mod+dp[i-1][2]*cnt[2]%mod)%mod;
dp[i][2]=(dp[i-1][0]*cnt[2]%mod+dp[i-1][1]*cnt[1]%mod+dp[i-1][2]*cnt[0]%mod)%mod;
}
cout<<dp[n][0]%mod<<endl;
return 0;
}
滚动数组优化dp思路:
可以看出第(i)层的状态只跟第(i-1)层的状态优化,考虑用滚动数组将空间优化。
(本题不必要优化)
滚动数组优化dp代码:
const ll mod=1e9+7;
ll cnt[3],dp[2][3];
int main(){
ll n=read,l=read,r=read;
cnt[0]=(r+3)/3-(l+2)/3; //%3==0
cnt[1]=(r+2)/3-(l+1)/3;//%3==1
cnt[2]=(r+1)/3-l/3;//%3==2
dp[0][0]=1;
for(int i=1;i<=n;i++){
dp[i&1][0]=(dp[(i-1)&1][0]*cnt[0]%mod+dp[(i-1)&1][1]*cnt[2]%mod+dp[(i-1)&1][2]*cnt[1]%mod)%mod;
dp[i&1][1]=(dp[(i-1)&1][0]*cnt[1]%mod+dp[(i-1)&1][1]*cnt[0]%mod+dp[(i-1)&1][2]*cnt[2]%mod)%mod;
dp[i&1][2]=(dp[(i-1)&1][0]*cnt[2]%mod+dp[(i-1)&1][1]*cnt[1]%mod+dp[(i-1)&1][2]*cnt[0]%mod)%mod;
}
cout<<dp[n&1][0]%mod<<endl;
return 0;
}
矩阵快速幂优化思路:
参考
由于转移过程中(cnt)数组的值是不变的,可以考虑用矩阵快速幂去优化。
矩阵快读幂优化代码:
const int maxn=2e5+100;
const ll mod=1e9+7;
struct matrix{
ll x,y;
ll num[3][3];
matrix operator * (const matrix b)const
{
matrix res;
memset(res.num,0,sizeof(res.num));
res.x=x;res.y=b.y;
for(int k=0;k<y;k++)
for(int i=0;i<x;i++)
for(int j=0;j<b.y;j++)
res.num[i][j]=(res.num[i][j]+num[i][k]*b.num[k][j]%mod)%mod;
return res;
}
void init(){
for(int i=0;i<3;i++) num[i][i]=1;
}
};
matrix pow_mat(matrix a,long long b)
{
matrix res;
memset(res.num,0,sizeof(res.num));
res.x=res.y=a.x;
res.init();
while(b)
{
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
matrix res,ans;
ll cnt[3];
int main(){
ll m=read,l=read,r=read;
cnt[0]=(r+3)/3-(l+2)/3; //%3==0
cnt[1]=(r+2)/3-(l+1)/3;//%3==1
cnt[2]=(r+1)/3-l/3;//%3==2
res.x=res.y=3;
res.num[0][0]=res.num[1][1]=res.num[2][2]=cnt[0];
res.num[0][1]=res.num[1][2]=res.num[2][0]=cnt[1];
res.num[0][2]=res.num[1][0]=res.num[2][1]=cnt[2];
ans.x=1;ans.y=3;
ans.num[0][0]=1;
ans=ans*pow_mat(res,m);
cout<<ans.num[0][0]<<endl;
return 0;
}
但是好像这个题的优化也用处不大~