luogu P5371 [SNOI2019]纸牌

打麻将+1(雾

有顺子这种东西...注意到以某个位置为开头的顺子数量最多为2,那么有个想法就是枚举以每个位置为开头的顺子个数,然后每个位置的刻子的取法个数为$\lceil\frac{\text{剩下的牌数}}{3}\rceil$,乘起来,然后每种情况的和就是答案

所以设$f_{i,j,k}$表示放到$i$牌,有$j$个$i-1,i,i+1$以及$k$个$i,i+1,i+2$的方案.转移枚举下一位放多少顺子(注意最后两个位置只能放0个),然后乘上刻子的取法个数进行转移,因为有些位置必须要用一些牌,所以方案应该改为(下面$x$为这一位用顺子消耗的牌数,$a$为这一位至少要用的牌数)$$\begin{cases}\lceil\frac{c-x}{3}\rceil&,x\ge a\\lceil\frac{c-(x+3 \lceil\frac{a-x}{3}\rceil)}{3}\rceil&,x< a\end{cases}$$

然后注意到$n$很大,并且很多位置都是随便用任意张牌,然后有限制的地方很少,所以有限制的地方以及最后两位暴力转移,剩下的地方矩乘转移

// luogu-judger-enable-o2

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define db double

using namespace std;

const int N=1000+10,mod=998244353;

LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

struct matrix

{

    int a[9][9];

    matrix(){memset(a,0,sizeof(a));}

    matrix operator * (const matrix &bb) const

    {

        matrix an;

        for(int i=0;i<9;++i)

            for(int j=0;j<9;++j)

            {

                LL nw=0;

                for(int k=0;k<9;++k) nw+=1ll*a[i][k]*bb.a[k][j];

                an.a[i][j]=nw%mod;

            }

        return an;

    }

    matrix operator ^ (const LL &bb) const

   	{

        matrix an,a=*this;

        for(int i=0;i<9;++i) an.a[i][i]=1;

        LL b=bb;

        while(b)

        {

            if(b&1) an=an*a;

            a=a*a,b>>=1;

        }

        return an;

    }

}aa,bb;

LL n,a[N][2];

int c,m,id[3][3],tmp[9];

int main()

{

    n=rd(),c=rd(),m=rd();

    for(int i=1;i<=m;++i) a[i][0]=rd(),a[i][1]=rd();

    a[m+1][0]=n+1;

    int ii=0;

    aa.a[0][0]=1;

    for(int i=0;i<3;++i)

        for(int j=0;j<3;++j)

            id[i][j]=i*3+j;

    for(int i=0;i<3;++i)

        for(int j=0;j<3;++j)

            for(int k=0;k<3;++k)

                bb.a[id[i][j]][id[j][k]]=max((c-i-j-k+3)/3,0);

    for(;ii<=m;)

    {

        LL l=max(min(n-2,a[ii+1][0]-1)-(a[ii][0]+1)+1,0ll);

        aa=aa*(bb^l);

        ++ii;

        if(a[ii][0]>n-2) break;

        memset(tmp,0,sizeof(tmp));

        for(int i=0;i<3;++i)

            for(int j=0;j<3;++j)

                for(int k=0;k<3;++k)

                {

                    int num=i+j+k<=a[ii][1]?i+j+k+(a[ii][1]-i-j-k+2)/3*3:i+j+k;

                    tmp[id[j][k]]=(tmp[id[j][k]]+1ll*aa.a[0][id[i][j]]*max((c-num+3)/3,0)%mod)%mod;

                }

        memcpy(aa.a[0],tmp,sizeof(tmp));

    }

    for(int i=0;i<3;++i)

        for(int j=0;j<3;++j)

            for(int k=1;k<3;++k)

                bb.a[id[i][j]][id[j][k]]=0;

    for(LL h=n-1;h<=n;++h,++ii)

    {

        while(h<=n&&h<a[ii][0]) aa=aa*bb,++h;

        if(h>n) break;

        memset(tmp,0,sizeof(tmp));

        for(int i=0;i<3;++i)

            for(int j=0;j<3;++j)

            {

                int num=i+j<=a[ii][1]?i+j+(a[ii][1]-i-j+2)/3*3:i+j;

                tmp[id[j][0]]=(tmp[id[j][0]]+1ll*aa.a[0][id[i][j]]*max((c-num+3)/3,0)%mod)%mod;

            }

        memcpy(aa.a[0],tmp,sizeof(tmp));

    }

    printf("%d\n",aa.a[0][0]);

    return 0;

}

巴特西

luogu P5371 [SNOI2019]纸牌

最新文章

热门文章