#354580 (C++17) No.840 ほむほむほむら

• 問題: No.840 ほむほむほむら
• ユーザー: LayCurse
• 提出日時: 2019-06-28 20:20:03
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 865 ms / 4,000 ms
• コード長: 8,986 bytes
• コンパイル時間: 2,226 ms
• コンパイル使用メモリ: 205,996 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-02 04:16:26
• 合計ジャッジ時間: 7,634 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	4 ms; 5,376 KB
testcase_02	AC	18 ms; 5,376 KB
testcase_03	AC	117 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	5 ms; 5,376 KB
testcase_07	AC	39 ms; 5,376 KB
testcase_08	AC	217 ms; 5,376 KB
testcase_09	AC	5 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	8 ms; 5,376 KB
testcase_12	AC	60 ms; 5,376 KB
testcase_13	AC	558 ms; 5,376 KB
testcase_14	AC	72 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	11 ms; 5,376 KB
testcase_17	AC	132 ms; 5,376 KB
testcase_18	AC	717 ms; 5,376 KB
testcase_19	AC	865 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	3 ms; 5,376 KB
testcase_22	AC	12 ms; 5,376 KB
testcase_23	AC	831 ms; 5,376 KB
testcase_24	AC	12 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	17 ms; 5,376 KB
testcase_27	AC	827 ms; 5,376 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
void *wmem;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
struct modint{
  static unsigned md;
  unsigned val;
  modint(){
  }
  modint(int a){
    val = ord(a);
  }
  modint(unsigned a){
    val = ord(a);
  }
  modint(long long a){
    val = ord(a);
  }
  modint(unsigned long long a){
    val = ord(a);
  }
  void setmod(unsigned m){
    md = m;
  }
  unsigned ord(unsigned a){
    return a%md;
  }
  unsigned ord(int a){
    a %= md;
    if(a < 0){
      a += md;
    }
    return a;
  }
  unsigned ord(unsigned long long a){
    return a%md;
  }
  unsigned ord(long long a){
    a %= md;
    if(a < 0){
      a += md;
    }
    return a;
  }
  unsigned get(){
    return val;
  }
  modint &operator+=(modint a){
    val += a.val;
    if(val >= md){
      val -= md;
    }
    return *this;
  }
  modint &operator-=(modint a){
    if(val < a.val){
      val = val + md - a.val;
    }
    else{
      val -= a.val;
    }
    return *this;
  }
  modint &operator*=(modint a){
    val = ((unsigned long long)val*a.val)%md;
    return *this;
  }
  modint &operator/=(modint a){
    return *this *= a.inverse();
  }
  modint operator+(modint a){
    return modint(*this)+=a;
  }
  modint operator-(modint a){
    return modint(*this)-=a;
  }
  modint operator*(modint a){
    return modint(*this)*=a;
  }
  modint operator/(modint a){
    return modint(*this)/=a;
  }
  modint operator+(int a){
    return modint(*this)+=modint(a);
  }
  modint operator-(int a){
    return modint(*this)-=modint(a);
  }
  modint operator*(int a){
    return modint(*this)*=modint(a);
  }
  modint operator/(int a){
    return modint(*this)/=modint(a);
  }
  modint operator+(long long a){
    return modint(*this)+=modint(a);
  }
  modint operator-(long long a){
    return modint(*this)-=modint(a);
  }
  modint operator*(long long a){
    return modint(*this)*=modint(a);
  }
  modint operator/(long long a){
    return modint(*this)/=modint(a);
  }
  modint operator-(void){
    modint res;
    if(val){
      res.val=md-val;
    }
    else{
      res.val=0;
    }
    return res;
  }
  operator bool(void){
    return val!=0;
  }
  operator int(void){
    return get();
  }
  operator long long(void){
    return get();
  }
  modint inverse(){
    int a=val, b=md, t, u=1, v=0;
    modint res;
    while(b){
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if(u < 0){
      u += md;
    }
    res.val = u;
    return res;
  }
  modint pw(unsigned long long b){
    modint a(*this), res;
    res.val = 1;
    while(b){
      if(b&1){
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  bool operator==(int a){
    return ord(a)==val;
  }
  bool operator!=(int a){
    return ord(a)!=val;
  }
}
;
modint operator+(int a, modint b){
  return modint(a)+=b;
}
modint operator-(int a, modint b){
  return modint(a)-=b;
}
modint operator*(int a, modint b){
  return modint(a)*=b;
}
modint operator/(int a, modint b){
  return modint(a)/=b;
}
modint operator+(long long a, modint b){
  return modint(a)+=b;
}
modint operator-(long long a, modint b){
  return modint(a)-=b;
}
modint operator*(long long a, modint b){
  return modint(a)*=b;
}
modint operator/(long long a, modint b){
  return modint(a)/=b;
}
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(modint x){
  int i;
  i = (int)x;
  wt_L(i);
}
template<class T> struct Matrix{
  T *dat;
  int c, mem, r;
  Matrix(){
    r=c=mem = 0;
  }
  Matrix(const int rr, const int cc){
    if(rr == 0 || cc == 0){
      r = c = 0;
    }
    else{
      r = rr;
      c = cc;
    }
    mem = r * c;
    if(mem > 0){
      dat = new T[mem];
    }
  }
  Matrix(const Matrix<T> &a){
    int i;
    r = a.r;
    c = a.c;
    mem = r * c;
    dat = new T[mem];
    for(i=0;i<mem;i++){
      dat[i] = a.dat[i];
    }
  }
  ~Matrix(){
    if(mem){
      delete [] dat;
    }
  }
  void changeSize(const int rr, const int cc){
    if(rr==0 || cc==0){
      r = c = 0;
    }
    else{
      r = rr;
      c = cc;
    }
    if(mem < r*c){
      if(mem){
        delete [] dat;
      }
      mem = r*c;
      dat = new T[mem];
    }
  }
  Matrix<T>& operator=(const Matrix<T> &a){
    int i, j;
    r = a.r;
    c = a.c;
    mem = r * c;
    dat = new T[mem];
    for(i=0;i<mem;i++){
      dat[i] = a.dat[i];
    }
    return *this;
  }
  Matrix<T>& operator=(const int a){
    int i, j;
    j = r * c;
    for(i=0;i<j;i++){
      dat[i] = 0;
    }
    j =min_L(r, c);
    for(i=0;i<j;i++){
      dat[i*c+i] = a;
    }
    return *this;
  }
  Matrix<T>& operator+=(const Matrix<T> &a){
    int i, j;
    if(r==0 || r!=a.r || c!=a.c){
      changeSize(0,0);
      return *this;
    }
    j = r*c;
    for(i=0;i<j;i++){
      dat[i] += a.dat[i];
    }
    return *this;
  }
  Matrix<T> operator+(const Matrix<T> &a){
    return Matrix<T>(*this) += a;
  }
  Matrix<T>& operator-=(const Matrix<T> &a){
    int i, j;
    if(r==0 || r!=a.r || c!=a.c){
      changeSize(0,0);
      return *this;
    }
    j = r*c;
    for(i=0;i<j;i++){
      dat[i] -= a.dat[i];
    }
    return *this;
  }
  Matrix<T> operator-(const Matrix<T> &a){
    return Matrix<T>(*this) -= a;
  }
  Matrix<T>& operator*=(const Matrix<T> &a){
    T *m;
    int i, j, k, x;
    if(r==0 || c!=a.r){
      changeSize(0,0);
      return *this;
    }
    m = (T*)wmem;
    x = r * a.c;
    for(i=0;i<x;i++){
      m[i] = 0;
    }
    for(i=0;i<r;i++){
      for(k=0;k<c;k++){
        for(j=0;j<a.c;j++){
          m[i*a.c+j] += dat[i*c+k] * a.dat[k*a.c+j];
        }
      }
    }
    changeSize(r, a.c);
    for(i=0;i<x;i++){
      dat[i] = m[i];
    }
    return *this;
  }
  Matrix<T> operator*(const Matrix<T> &a){
    return Matrix<T>(*this) *= a;
  }
  Matrix<T>& operator*=(const int a){
    int i, j;
    j = r * c;
    for(i=0;i<j;i++){
      dat[i] *= a;
    }
    return *this;
  }
  Matrix<T>& operator*=(const long long a){
    int i, j;
    j = r * c;
    for(i=0;i<j;i++){
      dat[i] *= a;
    }
    return *this;
  }
  Matrix<T>& operator*=(const double a){
    int i, j;
    j = r * c;
    for(i=0;i<j;i++){
      dat[i] *= a;
    }
    return *this;
  }
  inline T* operator[](const int a){
    return dat+a*c;
  }
}
;
template<class T> Matrix<T> operator*(const int a, const Matrix<T> &b){
  return Matrix<T>(b)*=a;
}
template<class T> Matrix<T> operator*(const Matrix<T> &b, const int a){
  return Matrix<T>(b)*=a;
}
template<class T> Matrix<T> operator*(const long long a, const Matrix<T> &b){
  return Matrix<T>(b)*=a;
}
template<class T> Matrix<T> operator*(const Matrix<T> &b, const long long a){
  return Matrix<T>(b)*=a;
}
template<class T> Matrix<T> operator*(const double a, const Matrix<T> &b){
  return Matrix<T>(b)*=a;
}
template<class T> Matrix<T> operator*(const Matrix<T> &b, const double a){
  return Matrix<T>(b)*=a;
}
template<class T, class S> inline Matrix<T> pow_L(Matrix<T> a, S b){
  Matrix<T> res;
  int i, j;
  res.changeSize(a.r, a.c);
  res = 1;
  while(b){
    if(b&1){
      res *= a;
    }
    b >>= 1;
    a *= a;
  }
  return res;
}
template<class T> inline T pow3_L(T a){
  return a*a*a;
}
char memarr[96000000];
unsigned modint::md;
#define MD 998244353
int N;
int K;
int main(){
  Matrix<modint> m;
  int i, j, k, x;
  modint res;
  wmem = memarr;
  {
    modint x;
    x.setmod(MD);
  }
  rd(N);
  rd(K);
  m.changeSize(pow3_L(K),pow3_L(K));
  m = 0;
  for(i=0;i<K;i++){
    for(j=0;j<K;j++){
      for(k=0;k<K;k++){
        x =(((((i)*(K))+(j))*(K))+(k));
        m[x][(((((i)*(K))+(j))*(K))+((k+1)%K))] += 1;
        m[x][(((((i)*(K))+((j+k)%K))*(K))+(k))] += 1;
        m[x][((((((i+j)%K)*(K))+(j))*(K))+(k))] += 1;
      }
    }
  }
  (m = pow_L(m,N));
  res = 0;
  for(j=0;j<K;j++){
    for(k=0;k<K;k++){
      res += m[0][(((((0)*(K))+(j))*(K))+(k))];
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190626-1

// --- original code ---
// #define MD 998244353
// int N, K;
// {
//   int i, j, k, x;
//   modint res;
//   Matrix<modint> m;
// 
//   rd(N,K);
//   m.changeSize(K**3, K**3);
//   m = 0;
//   rep(i,K) rep(j,K) rep(k,K){
//     x = b[K](i,j,k);
//     m[x][ b[K](i,j,(k+1)%K) ] += 1;
//     m[x][ b[K](i,(j+k)%K,k) ] += 1;
//     m[x][ b[K]((i+j)%K,j,k) ] += 1;
//   }
//   m **= N;
// 
//   res = 0;
//   rep(j,K) rep(k,K) res += m[0][ b[K](0,j,k) ];
//   wt(res);
// }