結果

問題 No.840 ほむほむほむら
ユーザー LayCurseLayCurse
提出日時 2019-06-14 22:17:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 208 ms / 4,000 ms
コード長 8,444 bytes
コンパイル時間 2,170 ms
コンパイル使用メモリ 197,832 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-26 17:06:18
合計ジャッジ時間 4,084 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 8 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 8 ms
5,376 KB
testcase_08 AC 32 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 14 ms
5,376 KB
testcase_13 AC 122 ms
5,376 KB
testcase_14 AC 16 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 32 ms
5,376 KB
testcase_18 AC 160 ms
5,376 KB
testcase_19 AC 208 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 197 ms
5,376 KB
testcase_24 AC 4 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 190 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
void *wmem;
template<class T> void walloc1d(T **arr, int x, void **mem = &wmem){
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
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');
  }
}
char memarr[96000000];
struct llModMatrix{
  int c, mod, r;
  long long **data, limit;
  long long* operator[](int a){
    return data[a];
  }
  void malloc(int r, int c, int mod){
    int i;
    this->r=r;
    this->c=c;
    this->mod=mod;
    limit=((1ULL<<63)-1)-(unsigned long long)(mod-1)*(mod-1);
    data=(long long**)std::malloc(sizeof(long long*)*r);
    data[0]=(long long*)std::malloc(sizeof(long long)*r*c);
    for(i=1;i<r;i++){
      data[i]=data[i-1]+c;
    }
  }
  void* malloc(int r, int c, int mod, void *workMemory){
    int i;
    this->r=r;
    this->c=c;
    this->mod=mod;
    limit=((1ULL<<63)-1)-(unsigned long long)(mod-1)*(mod-1);
    data=(long long**)workMemory;
    data[0]=(long long*)(data+r);
    for(i=1;i<r;i++){
      data[i]=data[i-1]+c;
    }
    return (void*)(data[0]+r*c);
  }
  void free(void){
    std::free(data[0]);
    std::free(data);
  }
  void setIdentity(){
    int i, j;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]=0;
        if(i==j){
          data[i][j]=1;
        }
      }
    }
  }
  void setZero(){
    int i, j;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]=0;
      }
    }
  }
  void operator=(llModMatrix &a){
    int i, j;
    r=a.r;
    c=a.c;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]=a.data[i][j];
      }
    }
  }
  void operator+=(llModMatrix &a){
    int i, j;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]+=a.data[i][j];
        if(data[i][j]>=mod){
          data[i][j]-=mod;
        }
        if(data[i][j]<=-mod){
          data[i][j]+=mod;
        }
      }
    }
  }
  void operator-=(llModMatrix &a){
    int i, j;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]-=a.data[i][j];
        if(data[i][j]>=mod){
          data[i][j]-=mod;
        }
        if(data[i][j]<=-mod){
          data[i][j]+=mod;
        }
      }
    }
  }
  void mixed(void){
    int i, j;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        if(data[i][j]<0){
          data[i][j]+=mod;
        }
        if(data[i][j]&&rand()%2){
          data[i][j]-=mod;
        }
      }
    }
  }
  void add(llModMatrix &a, llModMatrix &b){
    int i, j;
    r=a.r;
    c=a.c;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]=a.data[i][j]+b.data[i][j];
        if(data[i][j]>=mod){
          data[i][j]-=mod;
        }
        if(data[i][j]<=-mod){
          data[i][j]+=mod;
        }
      }
    }
  }
  void sub(llModMatrix &a, llModMatrix &b){
    int i, j;
    r=a.r;
    c=a.c;
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        data[i][j]=a.data[i][j]-b.data[i][j];
        if(data[i][j]>=mod){
          data[i][j]-=mod;
        }
        if(data[i][j]<=-mod){
          data[i][j]+=mod;
        }
      }
    }
  }
  void mulll(llModMatrix &a, llModMatrix &b){
    int i, j, k;
    r=a.r;
    c=b.c;
    setZero();
    for(i=0;i<r;i++){
      for(k=0;k<a.c;k++){
        if(a.data[i][k]){
          for(j=0;j<c;j++){
            data[i][j]+=a.data[i][k]*b.data[k][j];
            if(data[i][j]>=limit||data[i][j]<=-limit){
              data[i][j]%=mod;
            }
          }
        }
      }
    }
    for(i=0;i<r;i++){
      for(j=0;j<c;j++){
        if(data[i][j]>=mod||data[i][j]<=-mod){
          data[i][j]%=mod;
        }
      }
    }
  }
  void pow(llModMatrix &a, unsigned long long b, void *workMemory){
    llModMatrix t1, t2;
    r=c=a.r;
    workMemory=t1.malloc(r,c,mod,workMemory);
    workMemory=t2.malloc(r,c,mod,workMemory);
    setIdentity();
    t1=a;
    while(b){
      if(b%2){
        t2=*this;
        this->mulll(t2,t1);
      }
      t2.mulll(t1,t1);
      t1=t2;
      b/=2;
    }
  }
}
;
int N;
int K;
int main(){
  int *D, i, j, k, res, sz, x, y, z;
  llModMatrix mt, pw;
  wmem = memarr;
  walloc1d(&D, 1);
  rd(N);
  rd(K);
  sz = K*K*K;
  mt.malloc(sz, sz, 998244353);
  pw.malloc(sz, sz, 998244353);
  for(i=0;i<sz;i++){
    for(j=0;j<sz;j++){
      mt[i][j] = 0;
    }
  }
  for(x=0;x<K;x++){
    for(y=0;y<K;y++){
      for(z=0;z<K;z++){
        i = (x * K + y) * K + z;
        j = (x * K + y) * K + ((z+1)%K);
        mt[i][j]++;
        j = (x * K + ((y+z)%K)) * K + z;
        mt[i][j]++;
        j = (((x+y)%K) * K + y) * K + z;
        mt[i][j]++;
      }
    }
  }
  pw.pow(mt, N, wmem);
  res = 0;
  x = 0;
  for(y=0;y<K;y++){
    for(z=0;z<K;z++){
      i = (x * K + y) * K + z;
      res += pw[0][i];
      res %= 998244353;
    }
  }
  if(res < 0){
    res += 998244353;
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190609-2 [beta]

// --- original code ---
// struct llModMatrix{
//   int r, c, mod; ll limit; ll **data;
//   ll* operator[](int a){return data[a];}
//   void malloc(int r, int c, int mod){int i;this->r=r;this->c=c;this->mod=mod;limit=((1ULL<<63)-1)-(ull)(mod-1)*(mod-1);data=(ll**)std::malloc(sizeof(ll*)*r);data[0]=(ll*)std::malloc(sizeof(ll)*r*c);REP(i,1,r)data[i]=data[i-1]+c;}
//   void* malloc(int r, int c, int mod, void *workMemory){int i;this->r=r;this->c=c;this->mod=mod;limit=((1ULL<<63)-1)-(ull)(mod-1)*(mod-1);data=(ll**)workMemory;data[0]=(ll*)(data+r);REP(i,1,r)data[i]=data[i-1]+c;return (void*)(data[0]+r*c);}
//   void free(void){std::free(data[0]);std::free(data);}
//   void setIdentity(){int i,j;rep(i,r)rep(j,c){data[i][j]=0;if(i==j)data[i][j]=1;}}
//   void setZero(){int i,j;rep(i,r)rep(j,c)data[i][j]=0;}
//   void operator=(llModMatrix &a){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c)data[i][j]=a.data[i][j];}
//   void operator+=(llModMatrix &a){int i,j;rep(i,r)rep(j,c){data[i][j]+=a.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
//   void operator-=(llModMatrix &a){int i,j;rep(i,r)rep(j,c){data[i][j]-=a.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
//   void mixed(void){int i,j;rep(i,r)rep(j,c){if(data[i][j]<0)data[i][j]+=mod;if(data[i][j]&&rand()%2)data[i][j]-=mod;}}
//   void add(llModMatrix &a, llModMatrix &b){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c){data[i][j]=a.data[i][j]+b.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
//   void sub(llModMatrix &a, llModMatrix &b){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c){data[i][j]=a.data[i][j]-b.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
//   void mulll(llModMatrix &a, llModMatrix &b){int i,j,k;r=a.r;c=b.c;setZero();rep(i,r)rep(k,a.c)if(a.data[i][k])rep(j,c){data[i][j]+=a.data[i][k]*b.data[k][j];if(data[i][j]>=limit||data[i][j]<=-limit)data[i][j]%=mod;}rep(i,r)rep(j,c)if(data[i][j]>=mod||data[i][j]<=-mod)data[i][j]%=mod;}
//   void pow(llModMatrix &a, ull b, void *workMemory){llModMatrix t1,t2;r=c=a.r;workMemory=t1.malloc(r,c,mod,workMemory);workMemory=t2.malloc(r,c,mod,workMemory);setIdentity();t1=a;while(b){if(b%2){t2=*this;this->mulll(t2,t1);}t2.mulll(t1,t1);t1=t2;b/=2;}}
// };
// 
// 
// int N, K;
// {
//   int i, j, k;
//   int x, y, z;
//   int sz, res;
// 
//   int *D;
//   walloc1d(&D, 1);
//   
//   rd(N,K);
//   llModMatrix mt, pw;
// 
//   sz = K*K*K;
//   mt.malloc(sz, sz, 998244353);
//   pw.malloc(sz, sz, 998244353);
// 
//   rep(i,sz) rep(j,sz) mt[i][j] = 0;
// 
//   rep(x,K) rep(y,K) rep(z,K){
//     i = (x * K + y) * K + z;
// 
//     j = (x * K + y) * K + ((z+1)%K);
//     mt[i][j]++;
//     j = (x * K + ((y+z)%K)) * K + z;
//     mt[i][j]++;
//     j = (((x+y)%K) * K + y) * K + z;
//     mt[i][j]++;
//   }
// 
//   pw.pow(mt, N, wmem);
// 
//   res = 0;
//   x = 0;
//   rep(y,K) rep(z,K){
//     i = (x * K + y) * K + z;
//     res += pw[0][i];
//     res %= 998244353;
//   }
//   if(res < 0) res += 998244353;
//   wt(res);
// }
0