P10035「FAOI-R2」Paint (A) 题解

· · 题解

P10035 题目

解题思路

一种不太寻常的解题方法。

我们可以先写一个暴力枚举的代码：

#include<bits/stdc++.h>
using namespace std;
const int p=1000000007;//暴力枚举时可以不开long long
int poww(int a,int b)//快速幂
{
    int s=1;
    while(b)
    {
        if(b&1)
            s=s*a%p;
        a=a*a%p;
        b>>=1;  
    }
    return s;
}
bool pd(int a)//判断V3(a)是否为奇数
{
    int x=a,i;
    while(x%3!=0)
        x/=3,i++;
    if(i%2==1)
        return true;
    return false;   
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,s1=0,s2=0;//计算两种方法所踩到的油漆个数
        cin>>n;
        for(int j=1;j<=poww(3,n);j++)
        {
            if(pd(j))
            {
                if(j%2==0)
                    s2=(s2+1)%p;
                else
                    s1=(s1+1)%p;
            }
            else
            {
                if(j%2==1)
                    s2=(s2+1)%p;
                else
                    s1=(s1+1)%p;                
            }   
        }
        cout<<min(s1,s2)<<"\n";
    }
    return 0;
}

用此代码可求出 N\in[1,6] 时的答案，答案分别为：1,4,13,40,121,364。

不难发现，n=2 时，答案为 3^1+3^0=4，n=3 时，答案为 3^2+3^1+3^0=13。

即答案为 3^{n-1}+3^{n-2}+…+3^0，也可以写成 \sum_{i=0}^{n-1}3^i。

很明显，这是一个共比为 3 等比数列，下面进行求和（知道等比数列求和公式的大佬可以跳过）。

设 A=3^{n-1}+3^{n-2}+…+3^0，则 3A=3^n+3^{n-1}+…+3^1。

最终得出 $2A=3^n-3^0$，则 $A=\frac{3^n-1}{2}$（具体证明在最后）。 用快速幂求出 $3^n$ 即可。 ### Code ```cpp #include<bits/stdc++.h> using namespace std; const long long p=1000000007;//不要忘了开long long long long r(long long a,long long b)//快速幂 { long long ss=1; while(b) { if(b&1) ss=ss*a%p; a=a*a%p; b>>=1; } return ss; } int main() { int t; cin>>t; for(int i=1;i<=t;i++) { long long n; cin>>n; long long s=r(3,n)%p-1;//计算出3的n-1次方 if(s<0) s=p-abs(s); s=s*(p-p/2)%p; cout<<s<<"\n"; } return 0; } ``` ### 证明 我们可以将 $\texttt{01}$ 串 $A,B,C$ 每 $6$ 个字符分成一段， 每一段分别设为 $\texttt{01}$ 串 $a,b,c$。 可以发现无论如何，$\operatorname {mc}(a,c)$ 和 $\operatorname {mc}(b,c)$ 的值均相等，都为 $3$。 但是 $3^n$ 并不是 $6$ 的倍数，会多出来一个长度为 $3$ 的 $\texttt {01}$ 串，而长度为 $3$ 的 $\texttt {01}$ 串的贡献至少为 $1$。 由此我们得出答案为：$\lfloor\frac{3^n}{6}\rfloor\times 3+1=\frac{3^n-3}{6}\times3+1=\frac{3^n-1}{2}$。