题解 CF1105C 【Ayoub and Lost Array】

· · 题解

虽然这题较简单，但我们还是考虑从暴力一点点优化。

做法一

我们考虑枚举每一位是多少，然后判断是否合法。

#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 余 0、1、2。同种数在此题是等价的，且这三种数的数量可以轻松统计。所以我们可以考虑枚举每一位 \mod 3 的余数，然后统计答案。

#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] 
#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]。

#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] 
#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)

由于本人水平有限，只能把复杂度优化到这里。欢迎各位大佬提出更优秀的做法。