题解：P5255 [JSOI2013] 美丽家园

yanqijin · 2024-04-07 13:06:37 · 题解

题目大意

有一个 N \times M 的地板，可以铺上一些黑白的砖，要求每个 2 \times 2 的区域里，颜色不能完全一样，问有多少种方案(N \le 10^{100} M \le 5)。

思路

首先看到 M 这么小，还要统计方案数，容易想到暴力 状压，枚举 i(i \le n)，j(j \le 2^m-1)，则 f_{i,j} =\sum_{s=1}^{2^m-1}f_{i-1,s}[s\text{和}j\text{合法}]。但是 N \le 10^{100}，这么大的数据范围，普通的状压承受不了，所以要用 矩阵快速幂 优化。

式子 [f_{1,0},f_{1,1},f_{1,2}\dots f_{1,2^m-2},f_{1,2^m-1}]\times C^{n-1}=[f_{n,0},f_{n,1},f_{n,2}\ldots f_{n,2^m-2},f_{n,2^m-1}]。其中矩阵 C 中，若 S'\to S 合法，则 C_{S',S}=1，否则 C_{S',S}=0。

时间复杂度 O(2^{3m}\log n)。

(记得高精度)。

Code

#include<cstdio>
using namespace std;
int n[105],m,p,c[32][32],x[32][32],ans[32],z=0,cnt;//高精度
void read(int &x) {//快读
    x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
}
void write(int x) {//快输
    if(x<0) putchar('-'),x=-x;
    int sta[100];
    int top=0;
    do {
        sta[top++]=x%10,x/=10;
    } while(x);
    while(top) putchar(sta[--top]+48);
    putchar('\n');
}
void cheng() {
    if(z==0) {
        for(int j=0; j<(1<<m); j++) {
            for(int j1=0; j1<(1<<m); j1++) {
                c[j][j1]=x[j][j1];
            }
        }
        z=1;
        return ;
    }
    int q[32][32];
    for(int j=0; j<(1<<m); j++) {
        for(int j1=0; j1<(1<<m); j1++) {
            q[j][j1]=c[j][j1];
            c[j][j1]=0;
        }
    }
    for(int j=0; j<(1<<m); j++) {
        for(int j1=0; j1<(1<<m); j1++) {
            for(int k=0; k<(1<<m); k++) {
                c[j][j1]=(c[j][j1]+q[j][k]*x[k][j1])%p;
            }
        }
    }
}
void cheng1() {
    int q[32][32],s[32][32];
    for(int j=0; j<(1<<m); j++) {
        for(int j1=0; j1<(1<<m); j1++) {
            q[j][j1]=x[j][j1];
            s[j][j1]=x[j][j1];
            x[j][j1]=0;
        }
    }
    for(int j=0; j<(1<<m); j++) {
        for(int j1=0; j1<(1<<m); j1++) {
            for(int k=0; k<(1<<m); k++) {
                x[j][j1]=(x[j][j1]+q[j][k]*s[k][j1])%p;
            }
        }
    }
}
void qpow() {//矩阵快速幂
    while(cnt) {
        if(n[1]&1) {
            cheng();
        }
        cheng1();
        long long s=0,d=cnt;
        for(int i=cnt; i>=1; i--) {
            n[i]+=s*10;
            s=n[i]&1;
            n[i]>>=1;
        }
        cnt=0;
        for(int i=1; i<=d; i++) {
            if(n[i]) cnt=i;
        }
    }
}
int main() {
    char ch=0;
    while(ch<'0'||ch>'9') {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        n[++cnt]=ch-48;
        ch=getchar();
    }
    int h[105];
    for(int j=1; j<=cnt; j++) h[j]=n[j];
    for(int j=1; j<=cnt; j++) n[j]=h[cnt-j+1];
    read(m);
    read(p);
    if(p==1) {
        write(0);
        return 0;
    }
    for(int j=0; j<(1<<m); j++) {
        for(int j1=0; j1<(1<<m); j1++) {
            int a=j,d=j1;
            bool q=1;
            for(int s=1; s<m; s++) {
                if((a&1)==(d&1) and ((a>>1)&1)==((d>>1)&1) and (a&1)==((a>>1)&1)) q=0;
                a>>=1;
                d>>=1;
            }
            if(q) {
                x[j][j1]=1;
            }
        }
    }
    n[1]--;
    int v=1;
    while(n[v]<0) {
        n[v]+=10;
        n[v+1]--;
        v++;
    }
    qpow();
    for(int j1=0; j1<(1<<m); j1++) {
        for(int k=0; k<(1<<m); k++) {
            ans[j1]+=c[k][j1];
        }
    }
    int sum=0;
    for(int i=0; i<1<<m; i++) {
        sum=(sum+ans[i])%p;
    }
    write(sum);//输出
    return 0;
}