ASC1 E-Nice Patterns Strike Back

传送门（codeforces GYM）
题意：
给你一个n*m的矩形，对其进行上色，要求每个2*2的小正方形中的颜色不能相同，求方案数模p。（n<=10100,m<=5,p<=10000）

Solution:
看到计数题，首先考虑组合数或者dp，组合数发现行不通，考虑dp，发现m非常小，说明可以状压，又发现n非常大，说明一定是可以用矩阵乘法的，我们很快可以想出一个状态：f[i][S]表示第i列的状态为S的方案数，我们可以预处理出S可以由哪些状态转移过来，假设a[i][j]表示i和j是否可以合法的拼在一起，那么转移方程为：

f [i] [S] = \sum T = 0 T < (1 ≪ m) (f [i - 1] [T] * a [T] [S])

显然这是可以矩乘的，加上高精度的时间复杂度为

O(23mlogn∗len(n)) O ( 2 3 m log ⁡ n ∗ l e n ( n ) )

总结：这道题思考起来并不难，但是是一道综合好题。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
char ch[110];
struct bigint{
    int s[10100];
    int len;
    bool zf;
    bigint()
    {
        memset(s,0,sizeof(s));
        len=0;
        zf=0;
    }
    void init()
    {
        len=strlen(ch);
        if (ch[1]=='-')
        {
            zf=1;
            for (int i=2;i<=len;i++)
                s[i]=ch[len-i]-'0';
        }
        else
        {
            for (int i=1;i<=len;i++)
                s[i]=ch[len-i]-'0';
        }
    }
    void reverse()
    {
        int t[10010];
        for (int i=1;i<=len;i++)
            t[i]=s[len-i+1];
        for (int i=1;i<=len;i++)
            s[i]=t[i];
    }
    void uni()
    {
        while (s[len]==0&&len>1)len--; 
    }
    void pr()
    {
        for (int i=len;i>=1;i--) printf("%d",s[i]);
    }
}x,y;
struct JZ{
    int x,y;
    int a[1<<5][1<<5];
    JZ()
    {
        x=0,y=0;
        memset(a,0,sizeof(a));
    }
    void pr()
    {
        for (int i=0;i<x;i++)
        {
            for (int j=0;j<y;j++)
                printf("%d ",a[i][j]);
            printf("\n");
        }
    }
}f,b;
int p;
bigint operator -(bigint x,bigint y)
{
    bigint nw;
    nw.len=max(x.len,y.len);
    for (int i=1;i<=nw.len;i++)
    {
        nw.s[i]+=x.s[i]-y.s[i];
        if (nw.s[i]<0) nw.s[i+1]--,nw.s[i]+=10;
    }
    while (nw.s[nw.len]==0&&nw.len>1)nw.len--;
    return nw;
}
bigint operator /(bigint x,int y)
{
    bigint sh;
    int nv=0;
    for (int i=1;i<=x.len;i++)
    {
        nv=nv*10+x.s[i];
        sh.s[++sh.len]=nv/y;
        nv=nv%y;
    }
    return sh;
}
JZ operator *(JZ a,JZ b)
{
    JZ c;
    c.x=a.x;
    c.y=b.y;
    for (int i=0;i<a.x;i++)
        for (int j=0;j<b.y;j++)
            for (int k=0;k<a.y;k++)
            {
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
            }
    return c;
}
JZ fast_pow(JZ a,bigint x)
{
    bool tag=0;
    JZ ans;
    for (;!(x.len==1&&x.s[1]==0);x=x/2,a=a*a)
    {
        x.reverse();
        x.uni();
        x.reverse();
        if (x.s[x.len]&1)
        {
            if (tag) ans=ans*a;
            else ans=a,tag=1;
        } 
    }
    return ans;
}
int main()
{
    freopen("nice.in","r",stdin);
    freopen("nice.out","w",stdout);
    scanf("%s",ch);
    y.len=1;
    y.s[1]=1;
    x.init();
    x=x-y;
    x.reverse();
    scanf("%d%d",&m,&p);
    n=(1<<m);
    f.x=1;f.y=n;
    b.x=n,b.y=n;
    for (int i=0;i<n;i++)
        f.a[0][i]=1;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
        {
            int t1=(i&j),t2=(i|j);
            bool f1=0,f2=0;
            for (int k=1;k<=m;k++)
            {
                if (t1&1)
                {
                    if (f1==1) {f2=1;break;}
                    f1=1;
                }
                else f1=0;
                t1>>=1;
            }
            f1=0;
            for (int k=1;k<=m;k++)
            {
                if ((t2&1)==0)
                {
                    if (f1==1) {f2=1;break;}
                    f1=1;
                }
                else f1=0;
                t2>>=1;
            }
            b.a[i][j]=f2^1;
        }
    b=fast_pow(b,x);
    f=f*b;
    int anss=0;
    for (int i=0;i<n;i++)
        anss=(anss+f.a[0][i])%p;
    printf("%d",anss);
}

PS：日常写错矩乘怎么破QAQ