沈凯云


私信TA

用户名:2497686061

访问量:132

签 名:

等  级
排  名 2179
经  验 1812
参赛次数 6
文章发表 4
年  龄 0
在职情况 学生
学  校 南京中医药大学
专  业

  自我简介:

解题思路:我的C实在是不行,打了好久才过的,我用的基本上是纯数学方法,因为题目给的周长范围最大为10的9次方,所以O(N)的复杂度应该是过不了的,得用O(logN)来写,写一个快速幂,这个代码细节很多,我试错试了好几次,改这些细节比写这些代码时间还长,废话不多说,说思路:

设周长=2i,首先应该得到一个递推公式, f[i] = 3f[i−1]−f[i−2]+(i-2),我是找规律找出来的,但不推荐找规律,我看下面的那位大哥的题解思路很强,我给他复制粘贴一下,这一块其实挺难想的,但到这里才是刚开始。

[左侧或右侧有一个1,那么把这个1删去,对应的方案数f[i−1]
左侧和右侧都有一个1, 删去两次,对应的方案数为f[i−2]
每一列都大于1,把最下面一层删去,对应的方案为f[i−1]
得到公式 f[i] = 3f[i−1]−f[i−2]
最后再减去矩形的方案为 (n / 2 −1)]

这一段是某位大哥的思路。

接下来我的做法应该和他不一样,根据这个递推公式f[i+2] = 3f[i+1]−f[i]+i(i是半周长),通过特征根+待定系数法,得到f[n]的通项公式:

2222.png

其中n是周长(注意上面的i和这里的n不是一个)

n肯定是偶数,所以n-3是奇数,所以设(1+根5)/2的(n-3)次方=(A+B根5)/2,则(根5-1)/2的(n-3)次方=(B根5-A)/2,他们一相加再除以根5,就只剩B了,所以我们要求的就是B。所以我们用一个数组A[2]来存A和B,然后用快速幂求最终的A和B。我觉得我的这段代码应该是比较好懂的。

但是但是,特别要注意的是你会发现我在快速幂那一段代码全部是模的2X(X=987654321),这是因为奇偶性的问题,我们发现

((A+B根5)/2)*((C+D根5)/2)=(E+F根5)/2

如果A和B同奇偶,C和D同奇偶,那么E和F同奇偶,这个展开即证,而且A和B初始值都是1,是同奇偶的,所以A和B永远同奇偶,但是问题是,

模完987654321后,就不一定同奇偶了,因为987654321这是一个奇数(重点),比如说进行一次操作后A=C+2X(C<X),B=D+X(D<X)那么模987654321后A减去一个偶数,而B减去一个奇数,就不同奇偶了,所以要模2X,在最后的最后再模X。(我一开始没注意到,发现跑着跑着不同奇偶了)

另一个亲身经历,觉得需要注意的点就是,小心运算中某个数会爆掉,虽然我们用的long long,但是X=987654321是个九位数,而long long 的最大值是一个十九位数,X平方再乘个数就会爆掉(心酸),我当时想要不要写个大数运算,但我不会也很麻烦,后来发现我这个程序里最容易爆掉的一行是这里

temp[0]=(((a[0]*a[0]+a[1]*a[1])/2)%(2*X)+2*((a[1]*a[1])%(2*X)))%(2*X);

这是改之后的,一开始我的代码是这样的

temp[0]=((a[0]*a[0]+5*a[1]*a[1])/2)%(2*X);

发现5*a[1]*a[1]这个东西特别容易爆,a[1]最大是2*987654321-1,约等于2*(10的9次方),平方之后乘5就会到2*(10的20次方),会爆,所以我选择把这个乘5分开来写,2*a[1]*a[1]这个东西很接近极限范围,但不会爆,所以我改成了上面的那个写法。

那下面来看一下代码好咯。

注意事项:
注释掉的几行可以看一下运行过程
参考代码:

#include <stdio.h>

#include <stdlib.h>

const X=987654321;

long long A[2];

void f0(long long a[2]){

A[0]=1;

A[1]=1;

}

long long f1(long long a[2]){

long long temp[2];

temp[0]=(((a[0]*a[0]+a[1]*a[1])/2)%(2*X)+2*((a[1]*a[1])%(2*X)))%(2*X);

temp[1]=(a[0]*a[1])%(2*X);

a[0]=temp[0],a[1]=temp[1];

//printf("%lld %lld\n",a[0],a[1]);

}

long long f2(long long a[2]){

long long temp[2];

temp[0]=((a[0]+5*a[1])/2)%(2*X);

temp[1]=((a[0]+a[1])/2)%(2*X);

a[0]=temp[0],a[1]=temp[1];

//printf("%lld %lld\n",a[0],a[1]);

}

int f3(int n){

int m=0;

while(n){

    n>>=1;

    m++;

}

return m;

}

int main()

{

    long long sum;

    int n;

    while((scanf("%d", &n)) != EOF && n != 0){

        if(n<8||n%2==1)printf("0\n");

        else{

            f0(A);

            int m=n-3;

            int p=f3(m)-1;

            int x=1;//这里的x没用,只是用来看运行过程

            while(p>=1){

            if (m&(1<<(p-1))){f1(A);f2(A);x=2*x+1;

            //printf("%d\n",x);

            }

            else {f1(A);x*=2;

            //printf("%d\n",x);

            }

            p--;

            }

            sum=(A[1]-n/2+1+2*X)%X;

            printf("%lld\n",sum);

        }

    }

    return 0;

}


 

0.0分

1 人评分

  评论区