题解 CF1105C 【Ayoub and Lost Array】
BFLSTiger
2019-11-02 10:57:25
虽然这题较简单，但我们还是考虑从暴力一点点优化。
## 做法一
我们考虑枚举每一位是多少，然后判断是否合法。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
namespace Dango
{
const int MAXN=200005,MOD=1000000007;
int n,l,r;
long long ans;
int read()
{
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
void dfs(int a)
{
static long long sum;
if(a>n)
{
if(!(sum%3))
{
ans++;
if(ans>=MOD)ans-=MOD;
}
return;
}
for(int i=l;i<=r;i++)
{
sum+=i;
dfs(a+1);
sum-=i;
}
}
int work()
{
n=read();l=read();r=read();
dfs(1);
printf("%lld",ans);
return 0;
}
}
int main()
{
return Dango::work();
}
```
时间复杂度：$O((r-l)^n)$
空间复杂度：$O(n)$
## 做法二
我们仔细想了想忽然发现，根据题目要求，所有数可以分成三种：$mod$ $3$ 余 $1$、$2$、$3$。同种数在此题是等价的，且这三种数的数量可以轻松统计。所以我们可以考虑枚举每一位$mod$ $3$的余数，然后统计答案。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
namespace Dango
{
const int MAXN=200005,MOD=1000000007;
int n,l,r,cnt[3];
long long ans;
int read()
{
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
long long pow_(long long a,long long b)
{
long long res=1;
while(b)
{
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
void dfs(int a)
{
static long long sum,res=1;
if(a>n)
{
if(!sum)ans=(ans+res)%MOD;
return;
}
for(int i=0;i<3;i++)
{
if(!cnt[i])continue;
sum=(sum+i)%3;
res=res*cnt[i]%MOD;
dfs(a+1);
res=res*pow_(cnt[i],MOD-2)%MOD;
sum=(sum-i+3)%3;
}
}
int work()
{
n=read();l=read();r=read();
cnt[0]=(r+3)/3-(l+2)/3;
cnt[1]=(r+2)/3-(l+1)/3;
cnt[2]=(r+1)/3-l/3;
dfs(1);
printf("%lld",ans);
return 0;
}
}
int main()
{
return Dango::work();
}
```
时间复杂度：$O(3^n)$
空间复杂度：$O(n)$
## 做法三
过了几分钟，我们又发现这题可以 $dp$ 。我们设 $dp[i][j]$ 表示前 $i$ 个数的和 $mod$ $3$ 余 $j$。转移显然：
$$dp[i][0]=dp[i-1][0]*cnt[0]+dp[i-1][1]*cnt[2]+dp[i-1][2]*cnt[1]$$
$$dp[i][1]=dp[i-1][0]*cnt[1]+dp[i-1][1]*cnt[0]+dp[i-1][2]*cnt[2]$$
$$dp[i][2]=dp[i-1][0]*cnt[2]+dp[i-1][1]*cnt[1]+dp[i-1][2]*cnt[0]$$
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
namespace Dango
{
const int MAXN=200005,MOD=1000000007;
int n,l,r,cnt[3];
long long dp[MAXN][3];
long long ans;
int read()
{
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
int work()
{
n=read();l=read();r=read();
cnt[0]=(r+3)/3-(l+2)/3;
cnt[1]=(r+2)/3-(l+1)/3;
cnt[2]=(r+1)/3-l/3;
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;
}
printf("%lld",dp[n][0]);
return 0;
}
}
int main()
{
return Dango::work();
}
```
时间复杂度：$O(n)$
空间复杂度：$O(n)$
#### 注：至此你已经可以AC此题，但我们仍将继续优化。
## 做法四
我们仔细看了看做法三里的$dp$转移方程，发现$dp[i]$只与$dp[i-1]$有关，我们可以直接将$dp[i][j]$滚存成$dp[0/1][j]$。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
namespace Dango
{
const int MAXN=200005,MOD=1000000007;
int n,l,r,cnt[3];
long long dp[2][3];
long long ans;
int read()
{
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
int work()
{
n=read();l=read();r=read();
cnt[0]=(r+3)/3-(l+2)/3;
cnt[1]=(r+2)/3-(l+1)/3;
cnt[2]=(r+1)/3-l/3;
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;
}
printf("%lld",dp[n&1][0]);
return 0;
}
}
int main()
{
return Dango::work();
}
```
时间复杂度：$O(n)$
空间复杂度：$O(1)$
## 做法五
过了几分钟我们发现，$dp$转移方程里$cnt$的值不变，我们可以考虑矩阵快速幂。我们可以构造出：
$$\left[\begin{matrix}dp[i-1][0] & dp[i-1][1] & dp[i-1][2]\end{matrix} \right] \times \left[\begin{matrix}cnt[0] & cnt[1] & cnt[2] \\ cnt[2] & cnt[0] & cnt[1]\\ cnt[1] & cnt[2] & cnt[0] \end{matrix}\right]=\left[\begin{matrix}dp[i][0] & dp[i][1] & dp[i][2]\end{matrix} \right]$$
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
namespace Dango
{
const int MOD=1000000007;
struct matrix
{
int x,y;
long long 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;
}
}res,ans;
int n,l,r;
int read()
{
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
matrix pow_(matrix a,long long b)
{
matrix res;
memset(res.num,0,sizeof(res.num));
res.x=res.y=a.x;
for(int i=0;i<res.x;i++)
res.num[i][i]=1;
while(b)
{
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int work()
{
n=read();l=read();r=read();
res.x=res.y=3;
res.num[0][0]=res.num[1][1]=res.num[2][2]=(r+3)/3-(l+2)/3;
res.num[0][1]=res.num[1][2]=res.num[2][0]=(r+2)/3-(l+1)/3;
res.num[0][2]=res.num[1][0]=res.num[2][1]=(r+1)/3-l/3;
ans.x=1;ans.y=3;
ans.num[0][0]=1;
ans=ans*pow_(res,n);
printf("%lld",ans.num[0][0]);
return 0;
}
}
int main()
{
return Dango::work();
}
```
时间复杂度：$O(\log n)$
空间复杂度：$O(1)$
### 由于本人水平有限，只能把复杂度优化到这里。欢迎各位大佬提出更优秀的做法。