#4379. 「SNOI2019」紙牌

題目：

有一副紙牌。牌一共有 $n$ 種，分別標(biāo)有 $1, 2, \dots , n$，每種有 $C$ 張。故這副牌共有 $nC$ 張。

三張連號的牌（$i, i+1, i+2$）或三張相同的牌 $(i,i,i)$ 可以組成一疊。如果一組牌可以分成若干（包括零）疊，就稱其為一組王牌。

你從牌堆中摸了一些初始牌。現(xiàn)在你想再挑出一些牌組成一組王牌，請問有多少種可能組成的王牌呢？答案對 $998244353$ 取模。

兩組牌相同當(dāng)且僅當(dāng)它們含有的每一種牌數(shù)量都相同。

思路：

看到數(shù)據(jù)范圍 $n\le 1e^{18}$ 大概猜到對于沒有初始牌的牌堆要么有顯然規(guī)律，要么就是矩乘。

對然后就矩乘了。

因?yàn)榇笥诘扔?$3$ 張的，我們可以在自己牌堆里自己湊成一組，對于要和其他種牌配對的只需要留至多比前一堆多三張的情況。

所以我們可以用一個 $3*3?$ 的狀態(tài)表示最后兩個牌堆的情況。

然后用矩陣表示狀態(tài)的轉(zhuǎn)移系數(shù)。

對于有初始牌的單獨(dú)構(gòu)造矩陣。

代碼：

#include<bits/stdc++.h> #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<<i)&y)Ans=Ans*po[i]; } int main() {n=read();c=read();m=read();Lg=log2(n)+1;for(int i=1;i<=m;i++)k[i]=read(),a[i]=read();for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)if(i+j+k<=c)po[0].a[i*3+j][j*3+k]=(c-i-j-k)/3+1;for(int i=1;i<=Lg;i++)po[i]=po[i-1]*po[i-1];Ans.a[0][0]=1;for(int x=1;x<=m;x++){ksm(k[x]-k[x-1]-1);//printf("!!%d ",Ans.a[0][0]);for(int i=0;i<9;i++)for(int j=0;j<9;j++)tmp.a[i][j]=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++){int now=i+j+k;if(now<a[x])now=a[x]+((now-a[x])%3+3)%3;if(now<=c)tmp.a[i*3+j][j*3+k]=(c-now)/3+1;}Ans=Ans*tmp;}ksm(n-k[m]);printf("%d\n",Ans.a[0][0]);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Jessie-/p/11015092.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的「SNOI2019」的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。