BZOJ2476:战场的数目 矩阵乘法+整数划分

思路:

首先注意到不允许出现矩形,而这个条件很难限制,不过我们可以将矩形也一起算进去,在最后减掉,因为矩形的数目是可以\(O(1)\)计算的.

接下来就是考虑令\(f_i\)表示周长为\(i\)的合法方案数.

我们考虑几种情况:

[1]左侧有一个高度为1的方块

[2]右侧有一个高度为1的方块

[3]左右两侧均没有一个高度为1的方块

对于[1][2],我们可以分别在左侧和右侧拿走一个方块使得周长减少2,对于[3],我们可以拿走下面的一层使得周长减少2.不难发现这些关系都是一一对应的.

下面考虑一个问题,如果一种形态是两侧均有一个方块,那么我们事实上是算了两遍的.所以我们需要减去这种情况.而显然这种情况与周长减少了4的情况一一对应.

因此我们有:\(f_i=3f_{i-2}-f_{i-4}\)

利用矩阵乘法即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
static const int mod=987654321;
struct Matrix{
    int w,h;LL d[2][2];
    Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
    inline void operator*=(const Matrix&B){
        Matrix C(w,B.h);
        register int i,j,k;
        for(i=0;i<C.w;++i)
            for(j=0;j<C.h;++j)
                for(k=0;k<h;++k)
                    C.d[i][j]=(C.d[i][j]+d[i][k]*B.d[k][j])%mod;
        *this=C;
    }
};
 
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        if(n<=3||n&1){puts("0");continue;}
        int t=n/2-1,res;
        if(t==1)res=1;else if(t==2)res=2;
        else{
            Matrix ans(1,2);ans.d[0][0]=1,ans.d[0][1]=2;
            Matrix add(2,2);add.d[0][0]=0,add.d[0][1]=-1,add.d[1][0]=1,add.d[1][1]=3;
            Matrix one(2,2);one.d[0][0]=one.d[1][1]=1;
            t-=2;for(;t;t>>=1,add*=add)if(t&1)one*=add;
            ans*=one;
            res=ans.d[0][1];
        }
        res=((LL)res-(n/2-1)+mod)%mod;
        printf("%d\n",res);
    }return 0;
}