长沙网络赛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>#define N 40#define ll long longll 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;}