一题rk4虐场真愉快
首先奇数的情况是不需要考虑相对的，我们可以写出一个显而易见的dp
我们称第一个点的颜色为\(1\)，令
\(dp[i][0]\)表示当前格子颜色不为\(1\)的方案数
\(dp[i][1]\)表示当前格子颜色为\(1\)的方案数
那么\(dp[1][1]=m\)，答案为\(dp[n][0]\)
转移很简单
对于偶数的情况，我们可以考虑每次决策相对的两个点的颜色
形象的说，就是将后半段环叠在前半段环的上面
就变成了一个\(2\times n\)的矩阵
那么我们称第一行第一个的颜色为\(1\)，第二行第一个的颜色为\(2\)，其他颜色为\(0\)
那么对于每一列有7种状态，转移一下即可
当然转移要用矩阵快速幂
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
// <A.cpp> - 08/28/16 19:04:31 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100001; const int INF=1e9; const int MOD=998244353; struct matrix{ int a[2][2]; matrix(){memset(a,0,sizeof(a));} int* operator [](int x){return a[x];} matrix operator *(matrix b){ matrix ans; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++)ans[i][j]=(ans[i][j]+1ll*a[i][k]*b[k][j])%MOD; return ans; } }ans,base; struct matrix2{ int a[7][7]; matrix2(){memset(a,0,sizeof(a));} int* operator [](int x){return a[x];} matrix2 operator *(matrix2 b){ matrix2 ans; for(int i=0;i<7;i++) for(int j=0;j<7;j++) for(int k=0;k<7;k++)ans[i][j]=(ans[i][j]+1ll*a[i][k]*b[k][j])%MOD; return ans; } }ans2,bs; int main(){ int n=gi(),m=gi(); if(m==1){ if(n==1){printf("1");return 0;} printf("0");return 0; } if(n&1){ n--; ans[0][1]=m; base[0][0]=m-2;base[0][1]=1;base[1][0]=m-1; while(n){ if(n&1)ans=ans*base; base=base*base; n>>=1; } printf("%d",ans[0][0]); }else{ n>>=1; ans2[0][1]=1ll*m*(m-1)%MOD; bs[0][0]=(m-3+1ll*(m-4)*(m-4))%MOD; bs[1][0]=bs[2][0]=1ll*(m-2)*(m-3)%MOD; bs[3][0]=bs[4][0]=bs[5][0]=bs[6][0]=1ll*(m-3)*(m-3)%MOD; bs[0][1]=bs[2][1]=bs[3][1]=bs[6][1]=1; bs[0][2]=bs[1][2]=bs[4][2]=bs[5][2]=1; bs[1][3]=bs[4][3]=bs[6][3]=m-2; bs[0][3]=bs[5][3]=m-3; bs[2][4]=bs[3][4]=bs[5][4]=m-2; bs[0][4]=bs[6][4]=m-3; bs[2][5]=bs[4][5]=bs[6][5]=m-2; bs[0][5]=bs[3][5]=m-3; bs[1][6]=bs[3][6]=bs[5][6]=m-2; bs[0][6]=bs[4][6]=m-3; while(n){ if(n&1)ans2=ans2*bs; bs=bs*bs; n>>=1; } printf("%d",ans2[0][2]); } return 0; } |
说点什么