[关闭]
@zzzc18 2017-09-24T08:45:38.000000Z 字数 1613 阅读 511

2017.09.23 涂色游戏

TEST


题目:

在此输入正文
image_1bqpg4bmutu61svh7nf1puefbjm.png-38.7kB

Solution:

这里采用颜色数来进行计数(不然岂不是不可做?)
然后就顺理成章地有了以下内容

image_1bqpg8om895ando17p51o0r7uf13.png-105.5kB
image_1bqpgdeuo18q31smbi4inc8t361g.png-94.9kB

上述算法复杂度是 显然不可接受
但是我们考虑 的过程就类似于矩阵的乘法()
这样,把 作为左边的矩阵, 作为右边的矩阵,答案就是

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. typedef long long LL;
  6. const LL MAXN = 109;
  7. const LL MOD = 998244353;
  8. LL n,m,p,q;
  9. LL C[MAXN][MAXN];
  10. LL f[MAXN][MAXN];
  11. LL g[MAXN];
  12. struct Matrix{
  13. LL num[MAXN][MAXN];
  14. Matrix(){
  15. memset(num,0,sizeof(num));
  16. }
  17. };
  18. Matrix operator * (Matrix A,Matrix B){
  19. LL i,j,k;
  20. Matrix re;
  21. for(i=1;i<=p;i++){
  22. for(j=1;j<=p;j++){
  23. for(k=1;k<=p;k++){
  24. re.num[i][j]=(re.num[i][j]+A.num[i][k]*B.num[k][j])%MOD;
  25. }
  26. }
  27. }
  28. return re;
  29. }
  30. LL qpow_num(LL x,LL k){
  31. LL i;
  32. LL re=1,tmp=x;
  33. for(i=1;i<=k;i<<=1){
  34. if(i&k){
  35. re*=tmp;
  36. re%=MOD;
  37. }
  38. tmp*=tmp;
  39. tmp%=MOD;
  40. }
  41. return re;
  42. }
  43. void INIT(){
  44. LL i,j;
  45. C[0][0]=1;
  46. for(i=1;i<MAXN;i++){
  47. C[i][0]=C[i][i]=1;
  48. for(j=1;j<i;j++){
  49. C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
  50. }
  51. }
  52. f[0][0]=1;
  53. for(i=1;i<MAXN;i++){
  54. for(j=1;j<MAXN;j++){
  55. f[i][j]=(f[i-1][j-1]*(p-(j-1))%MOD+f[i-1][j]*j%MOD)%MOD;
  56. }
  57. }
  58. for(i=0;i<MAXN;i++)
  59. g[i]=f[n][i];
  60. }
  61. LL calg(LL x){
  62. return g[x]*qpow_num(C[p][x],MOD-2)%MOD;
  63. }
  64. void solve(){
  65. Matrix ans,trans;
  66. for(int i=1;i<=p;i++)ans.num[1][i]=g[i];
  67. LL i,j,k;
  68. for(i=1;i<=p;i++){
  69. for(j=1;j<=p;j++){
  70. for(k=max(q,max(i,j));k<=min(p,i+j);k++){
  71. trans.num[i][j]=(trans.num[i][j]+C[i][i+j-k]*C[p-i][k-i])%MOD;
  72. }
  73. trans.num[i][j]=(calg(j)*trans.num[i][j])%MOD;
  74. }
  75. }
  76. m--;
  77. for(i=1;i<=m;i<<=1){
  78. if(m&i){
  79. ans=ans*trans;
  80. }
  81. trans=trans*trans;
  82. }
  83. LL ANS=0;
  84. for(i=1;i<=p;i++){
  85. ANS=(ANS+ans.num[1][i])%MOD;
  86. }
  87. printf("%lld\n",ANS);
  88. }
  89. int main(){
  90. freopen("color.in","r",stdin);
  91. freopen("color.out","w",stdout);
  92. scanf("%lld%lld%lld%lld",&n,&m,&p,&q);
  93. INIT();
  94. solve();
  95. return 0;
  96. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注