长沙市网络赛G,H

长沙网络赛G,H

最后时刻H因为几个代码细节问题导致没有通过，这场网络赛失败最大的责任恐怕就在我身上吧。。。。。另外G题比赛时没有明确的思路，耽误了不少时间。这样的表现只能用杯具来形容，感觉这场比赛坐下来，有些充满遗憾的感觉。。。。

G：

如何处理x+y+z = n呢？主要是一直感觉O(N^2)预处理会超时（后来竟然发现我机子太慢，同样的代码，在爱神的机子上运行<2s,在我的机子上就要运行3s+。。。）

后来队友也多次TLE，huyue学长又搞出神奇的东东。。。我就彻底撂下了，后来问了爱神，才知道原来可以n^2预处理是不会超时的。。。

首先要处理一个数可以拆成两个素数(可以允许相同)的解数，O(N^2)一下就好了。。。然后就是通过枚举第三个加数处理x+y+z的情况。复杂度O(n)，但是有个问题，可能会重复计算。若x!=y!=z，则重复计算了三次。如果有两个数相等，则重复计算了两次，若x=y=z，则没有重复计算。那就统一变成重复计算三次吧。由于两个数相等的情况可以拆成x+2*y=n

统计一下这样的情况有多少就可以了。附代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
 
#define N 80005
#define cl(a) memset(a,0,sizeof(a))
#define ss(a) scanf("%d",&a)
#define pb push_back
#define ll long long
#define mod 1000000007

using namespace std;

ll ispri[N],add[N],mul[N];
vector<int>pri;
 
void prime()
{
    int i,j;
    for (i=2;i<N;i++)
        if (!ispri[i])
        {
            pri.pb(i);
            for (j=i*2;j<N;j+=i) ispri[j]=1;
        }
}



void init()
{
    int i,j;
    for (i=0;i<pri.size();i++)
        for (j=i;j<pri.size()&&pri[i]+pri[j]<N;j++)
        {
            add[pri[i]+pri[j]]++;
            if (pri[i]>=N/pri[j]) mul[pri[i]*pri[j]]++;    
        }
}                 

ll addmul(int n,int &rep)
{
    int i;
    ll re=0;
    for (i=0;i<pri.size()&&pri[i]<=n;i++) 
    {
        if ((n-pri[i])%2==0) 
        {
            rep++;
            if (pri[i]*3==n) rep++;
        }     
        re=(re+mul[n-pri[i]])%mod;
    }
    return re;
}

ll thmul(int n)
{
    int m=n,t=0,i=0;
    while (m>1)
    {
        while (n%pri[i]==0)
        {
            m/=pri[i];
            t++;
        }
        if (t>=3) break;
    }
    if (t==3&&m==1) return 1;
}

ll thadd(int n,int rep)
{
    int i;
    ll re=0;
    for (i=1;i<n-1;i++) re+=add[n-i];
    re=(re+rep)/3;
    return re%mod;
}

int main()
{
    prime();
    init();
    int n,rep;
    ll res=0;
    while (cin>>n)
    {
        if (!ispri[n]) res++;
        res=(res+mul[n]+add[n])%mod;
        rep=0;
        res=(res+addmul(n,rep)+thmul(n)+thadd(n,rep))%mod;
        cout<<res<<endl;
    }
    return 0;
}

最遗憾的H题

话说我连题都没看，YRC把公式告诉了我，问我这个公式（int）（l+sqrt(l*(l-1))）^k mod k

K太大，直接算不行，要做处理

刚开始我也没有想起来，后来觉得在学斐波那契序列转换为线性模式时碰到了带根号问题的处理，在纸上划了划，果然是这样

由于(l-sqrt(l*(l-1))^k<1，所以等价成(l+sqrt(l*(l-1))^k + （l-sqrt(l*(l-1))-1

前面的处理方式，组合数学有介绍斐波那契数列如何写成线性表达式的做法，省略，大概就是用到一元二次方程。。

推出了公式f(n) = 2*l*f(n) -l*f(n)，并且模k

结果呢，矩阵快速幂写错了一点，另外取了k-1当模。。。。。。奇葩的代码。。。当然就杯具了。

这题要是当时AC了，就过关了。。

可是，现实就是这样，没有如果，你所做的只有努力去提升自己的实力，多敲代码。。。。改变自己代码风格上的不足来减少失误

#include <iostream>
#include <cstdio>

#define N 40
#define ll long long

ll a[N][3][3],f[3],mod;

using namespace std;

void init(ll l)
{
    a[0][1][1]=(2*l)%mod;a[0][1][2]=mod-l%mod;
    a[0][2][1]=1;a[0][2][2]=0;
    f[1]=2*l%mod;
    f[2]=2;
}

void rmul(ll x)
{
    int i,j,k;
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
        {
            ll res=0;
            for (k=1;k<=2;k++) res=(res+a[x-1][i][k]*a[x-1][k][j]%mod)%mod;
            a[x][i][j]=res; 
        }
}

void zmul(ll x)
{
    ll ff1=0,ff2=0;
    ff1=(f[1]*a[x][1][1]%mod+f[2]*a[x][1][2]%mod)%mod;
    ff2=(f[1]*a[x][2][1]%mod+f[2]*a[x][2][2]%mod)%mod;
    f[1]=ff1;
    f[2]=ff2;
}

void quick(ll k)
{
    //偏偏在这里写了mod=k,但这里的k是k-1啊。。。。 
    ll n=k,i=0;
    while (n>0)
    {
        if (n&1) zmul(i);
        i++;
        rmul(i);
        n>>=1; 
    }
}
  
int main()
{
    ll k,l;
    while (cin>>k>>l)
    {
        mod=k;    //刚开始我没有在这里对mod赋值 
        init(l);
        quick(k-1);
        cout<<(f[1]-1+mod)%mod<<endl;
    }
    return 0;
}

长沙市网络赛G,H

相关推荐