#4379. 「SNOI2019」纸牌

题目：

有一副纸牌。牌一共有 $n$ 种，分别标有 $1, 2, \dots , n$，每种有 $C$ 张。故这副牌共有 $nC$ 张。

三张连号的牌（$i, i+1, i+2$）或三张相同的牌 $(i,i,i)$ 可以组成一叠。如果一组牌可以分成若干（包括零）叠，就称其为一组王牌。

你从牌堆中摸了一些初始牌。现在你想再挑出一些牌组成一组王牌，请问有多少种可能组成的王牌呢？答案对 $998244353$ 取模。

两组牌相同当且仅当它们含有的每一种牌数量都相同。

思路：

看到数据范围 $n\le 1e^{18}$ 大概猜到对于没有初始牌的牌堆要么有显然规律，要么就是矩乘。

对然后就矩乘了。

因为大于等于 $3$ 张的，我们可以在自己牌堆里自己凑成一组，对于要和其他种牌配对的只需要留至多比前一堆多三张的情况。

所以我们可以用一个 $3*3​$ 的状态表示最后两个牌堆的情况。

然后用矩阵表示状态的转移系数。

对于有初始牌的单独构造矩阵。

代码：

#include
      
       #define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1005,p=998244353;int c,m,a[N],Lg;LL k[N],n;il LL read(){   LL x,f=1;char ch;   _(!)ch=='-'?f=-1:f;x=ch^48;   _()x=(x<<1)+(x<<3)+(ch^48);   return f*x;}il int mu(int x,int y){    return (x+y>=p)?x+y-p:x+y;}struct Mat{    int a[11][11];    Mat friend operator *(Mat t1,Mat t2){        Mat t3;        for(int i=0;i<9;i++)for(int j=0;j<9;j++)t3.a[i][j]=0;        for(int i=0;i<9;i++)for(int j=0;j<9;j++)for(int k=0;k<9;k++)            t3.a[i][j]=mu(t3.a[i][j],1ll*t1.a[i][k]*t2.a[k][j]%p);        return t3;    }}Ans,po[70],tmp;il void ksm(LL y){    for(int i=0;i<=Lg;i++)if((1ll<