【UOJ241】【UR#16】破坏发射台

一题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种状态，转移一下即可

当然转移要用矩阵快速幂

// <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;
}

// <A.cpp> - 08/28/16 19:04:31

// This file is created by XuYike's black technology automatically.

// 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;

}