5371

myee · 2023-02-01 11:00:22 · 题解

Update

抱歉标题写错了，重新交一下。

同时补充说明一下，关于后面 B 的大小，取 8 是因为这个东西本身就非常跑不满，以及可以用二进制优化常数。

前言

感觉这种计数，一看到，就很 dp 套 dp 啊！

就，感觉就是「ZJOI2019」麻将，的高清重制版呐！

思路

以下称 (i,i,i) 为刻子，(i,i+1,i+2) 为顺子，合法情形称为胡牌。

首先，一个牌取 v>6 的可行性，与 v-3 相同；也即，与 (v-4)\bmod3+4 相同。

因为，如果其有刻子，可以挖掉；如果没有，则由抽屉原理，有至少 3 个完全相同的顺子结构经过之，可以转化成刻子的情形然后仍然合法。

反过来，从 v-3 合法到 v 合法的推导，可以多加一个刻子。

因此可以理解为，其有 a_i 种取 i 张牌的方案，其中 i\in\{0,1,2,3,4,5,6\}。

这样就可以直接建“胡牌自动机”了。

即，我们记录其前面两种顺子分别有多少个（均为 0\sim2 个），经过某种时先除去前面两种顺子的贡献，然后把刻子尽可能多取，剩下的再作为顺子的起点；容易证明，任何一个牌的胡态都可以这么表述，且唯一表述。（感觉这么描述好抽象啊，但是想不出更好的描述了）

这样，每个牌的选法总数可以描述为一个线性变换，于是可以用矩阵乘法描述。

然后这样子，对相邻的牌之间的部分上矩阵快速幂，就做完了。

发现每个 i 处 DP 的状态是 3\times3=9 种的，所以矩阵都是 9\times9 的，做 O(X) 轮快速幂肯定没问题。

然后注意到 unsigned long long 允许我们开下 9\times998244352\times998244352 的大小，因此可以先求和再取模，大大减小了常数。

设 a=9，总复杂度即为 O(a^3X\log n)。

然后这个还是太逊了，考虑优化。

考虑倍增预处理 n 以内的矩阵快速幂，然后每次乘向量即可。

总复杂度 O(a^3\log n+a^2X\log n)，可以轻松通过。

然后就是考虑把普通倍增改为改为高进制快速幂，假设是 B 进制，则为 O((a^3B+{a^2X})\log_Bn)。

取 B=\Theta(\frac Xa)，复杂度即为 O(a^2X\log_{\frac Xa}n)。

Code

我取了 B=8。

跑得很快，目前是 loj 最优解。

const ullt Mod=998244353;
const uint Lim=9;
using Vec = ullt[Lim];
using Mat = Vec[Lim];
inline voi copy(Mat a,Mat b){
    for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)b[i][j]=a[i][j];
}
inline voi mul(Mat a,Mat b,Mat c){
    for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)
        for(uint k=0;k<Lim;k++)c[i][k]+=a[i][j]*b[j][k];
    for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)c[i][j]%=Mod;
}
inline voi muleq(Vec a,Mat b){
    static Vec c;
    for(uint i=0;i<Lim;i++)c[i]=0;
    for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)c[j]+=a[i]*b[i][j];
    for(uint i=0;i<Lim;i++)a[i]=c[i]%Mod;
}
Mat Base[25][8],M;Vec Ans;
ullt A[7];
voi update(uint n){
    if(!~n)A[0]=A[1]=A[2]=A[3]=A[4]=A[5]=A[6]=0;
    else if(n<=6)for(uint i=0;i<=6;i++)A[i]=n>=i;
    else A[0]=A[1]=A[2]=A[3]=1,A[4]=(n-1)/3,A[5]=(n-2)/3,A[6]=n/3-1;
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    ullt n;uint c,x;scanf("%llu%u%u",&n,&c,&x),update(c);
    for(uint i=0;i<=6;i++)for(uint j=0;j<=2;j++)for(uint k=0;k<=2;k++)if(j+k<=i)
        Base[0][1][j*3+k][k*3+(i-j-k)%3]+=A[i];
    for(uint i=0;;i++){
        static ullt v=1;
        mul(Base[i][1],Base[i][1],Base[i][2]);
        mul(Base[i][2],Base[i][1],Base[i][3]);
        mul(Base[i][3],Base[i][1],Base[i][4]);
        mul(Base[i][4],Base[i][1],Base[i][5]);
        mul(Base[i][5],Base[i][1],Base[i][6]);
        mul(Base[i][6],Base[i][1],Base[i][7]);
        if((v<<=3)>n)break;
        mul(Base[i][7],Base[i][1],Base[i+1][1]);
    }
    std::vector<std::pair<ullt,uint> >V(x);
    for(auto&s:V)scanf("%llu%u",&s.first,&s.second);
    std::sort(V.begin(),V.end());
    Ans[0]=1;
    ullt a=0;
    for(auto s:V){
        a=s.first-a-1;for(uint i=0;a;i++,a>>=3)if(a&7)muleq(Ans,Base[i][a&7]);
        a=s.first,copy(Base[0][1],M),update(s.second-1);
        for(uint i=0;i<=6;i++)for(uint j=0;j<=2;j++)for(uint k=0;k<=2;k++)if(j+k<=i)
            M[j*3+k][k*3+(i-j-k)%3]-=A[i];
        muleq(Ans,M);
    }
    a=n-a;for(uint i=0;a;i++,a>>=3)if(a&7)muleq(Ans,Base[i][a&7]);
    printf("%llu\n",Ans[0]);
    return 0;
}