#603959 (C++17) No.1340 おーじ君をさがせ

• 問題: No.1340 おーじ君をさがせ
• ユーザー: LayCurse
• 提出日時: 2021-01-15 21:46:42
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,098 ms / 2,000 ms
• コード長: 14,023 bytes
• コンパイル時間: 2,910 ms
• コンパイル使用メモリ: 221,580 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-05 21:43:40
• 合計ジャッジ時間: 18,236 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 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	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	188 ms; 5,376 KB
testcase_12	AC	28 ms; 5,376 KB
testcase_13	AC	137 ms; 5,376 KB
testcase_14	AC	408 ms; 5,376 KB
testcase_15	AC	344 ms; 5,376 KB
testcase_16	AC	23 ms; 5,376 KB
testcase_17	AC	107 ms; 5,376 KB
testcase_18	AC	198 ms; 5,376 KB
testcase_19	AC	11 ms; 5,376 KB
testcase_20	AC	4 ms; 5,376 KB
testcase_21	AC	199 ms; 5,376 KB
testcase_22	AC	541 ms; 5,376 KB
testcase_23	AC	198 ms; 5,376 KB
testcase_24	AC	1,087 ms; 5,376 KB
testcase_25	AC	19 ms; 5,376 KB
testcase_26	AC	11 ms; 5,376 KB
testcase_27	AC	9 ms; 5,376 KB
testcase_28	AC	28 ms; 5,376 KB
testcase_29	AC	3 ms; 5,376 KB
testcase_30	AC	209 ms; 5,376 KB
testcase_31	AC	1,076 ms; 5,376 KB
testcase_32	AC	1,000 ms; 5,376 KB
testcase_33	AC	980 ms; 5,376 KB
testcase_34	AC	878 ms; 5,376 KB
testcase_35	AC	1,098 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	3 ms; 5,376 KB
testcase_38	AC	1,069 ms; 5,376 KB
testcase_39	AC	281 ms; 5,376 KB
testcase_40	AC	279 ms; 5,376 KB
testcase_41	AC	277 ms; 5,376 KB
testcase_42	AC	2 ms; 5,376 KB
testcase_43	AC	2 ms; 5,376 KB
testcase_44	AC	2 ms; 5,376 KB
testcase_45	AC	2 ms; 5,376 KB
testcase_46	AC	208 ms; 5,376 KB
testcase_47	AC	222 ms; 5,376 KB
testcase_48	AC	243 ms; 5,376 KB
testcase_49	AC	242 ms; 5,376 KB
testcase_50	AC	238 ms; 5,376 KB
testcase_51	AC	243 ms; 5,376 KB
testcase_52	AC	473 ms; 5,376 KB
testcase_53	AC	457 ms; 5,376 KB
testcase_54	AC	462 ms; 5,376 KB
testcase_55	AC	356 ms; 5,376 KB
testcase_56	AC	2 ms; 5,376 KB
testcase_57	AC	2 ms; 5,376 KB
testcase_58	AC	2 ms; 5,376 KB
testcase_59	AC	142 ms; 5,376 KB
testcase_60	AC	2 ms; 5,376 KB
testcase_61	AC	139 ms; 5,376 KB

コンパイルメッセージ

In member function 'void Matrix<T>::changeSize(int, int) [with T = mint]',
    inlined from 'Matrix<T>& Matrix<T>::operator=(const Matrix<T>&) [with T = mint]' at main.cpp:518:15,
    inlined from 'int main()' at main.cpp:742:21:
main.cpp:506:9: warning: 'mt.Matrix<mint>::dat' may be used uninitialized [-Wmaybe-uninitialized]
  506 |         delete [] dat;
      |         ^~~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:729:16: note: 'mt.Matrix<mint>::dat' was declared here
  729 |   Matrix<mint> mt(N, N);
      |                ^~

ソースコード

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (1000000007U)
void*wmem;
char memarr[96000000];
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
struct Rand{
  unsigned x;
  unsigned y;
  unsigned z;
  unsigned w;
  Rand(void){
    x=123456789;
    y=362436069;
    z=521288629;
    w=(unsigned)time(NULL);
  }
  Rand(unsigned seed){
    x=123456789;
    y=362436069;
    z=521288629;
    w=seed;
  }
  inline unsigned get(void){
    unsigned t;
    t = (x^(x<<11));
    x=y;
    y=z;
    z=w;
    w = (w^(w>>19))^(t^(t>>8));
    return w;
  }
  inline double getUni(void){
    return get()/4294967296.0;
  }
  inline int get(int a){
    return (int)(a*getUni());
  }
  inline int get(int a, int b){
    return a+(int)((b-a+1)*getUni());
  }
  inline long long get(long long a){
    return(long long)(a*getUni());
  }
  inline long long get(long long a, long long b){
    return a+(long long)((b-a+1)*getUni());
  }
  inline double get(double a, double b){
    return a+(b-a)*getUni();
  }
  inline int getExp(int a){
    return(int)(exp(getUni()*log(a+1.0))-1.0);
  }
  inline int getExp(int a, int b){
    return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
  }
}
;
struct mint{
  static unsigned md;
  static unsigned W;
  static unsigned R;
  static unsigned Rinv;
  static unsigned mdninv;
  static unsigned RR;
  unsigned val;
  mint(){
    val=0;
  }
  mint(int a){
    val = mulR(a);
  }
  mint(unsigned a){
    val = mulR(a);
  }
  mint(long long a){
    val = mulR(a);
  }
  mint(unsigned long long a){
    val = mulR(a);
  }
  int get_inv(long long a, int md){
    long long t=a;
    long long s=md;
    long long u=1;
    long long v=0;
    long long e;
    while(s){
      e=t/s;
      t-=e*s;
      u-=e*v;
      swap(t,s);
      swap(u,v);
    }
    if(u<0){
      u+=md;
    }
    return u;
  }
  void setmod(unsigned m){
    int i;
    unsigned t;
    W = 32;
    md = m;
    R = (1ULL << W) % md;
    RR = (unsigned long long)R*R % md;
    switch(m){
      case 104857601:
      Rinv = 2560000;
      mdninv = 104857599;
      break;
      case 998244353:
      Rinv = 232013824;
      mdninv = 998244351;
      break;
      case 1000000007:
      Rinv = 518424770;
      mdninv = 2226617417U;
      break;
      case 1000000009:
      Rinv = 171601999;
      mdninv = 737024967;
      break;
      case 1004535809:
      Rinv = 234947584;
      mdninv = 1004535807;
      break;
      case 1007681537:
      Rinv = 236421376;
      mdninv = 1007681535;
      break;
      case 1012924417:
      Rinv = 238887936;
      mdninv = 1012924415;
      break;
      case 1045430273:
      Rinv = 254466304;
      mdninv = 1045430271;
      break;
      case 1051721729:
      Rinv = 257538304;
      mdninv = 1051721727;
      break;
      default:
      Rinv = get_inv(R, md);
      mdninv = 0;
      t = 0;
      for(i=(0);i<((int)W);i++){
        if(t%2==0){
          t+=md;
          mdninv |= (1U<<i);
        }
        t /= 2;
      }
    }
  }
  unsigned mulR(unsigned a){
    return (unsigned long long)a*R%md;
  }
  unsigned mulR(int a){
    if(a < 0){
      a = a%((int)md)+(int)md;
    }
    return mulR((unsigned)a);
  }
  unsigned mulR(unsigned long long a){
    return mulR((unsigned)(a%md));
  }
  unsigned mulR(long long a){
    a %= (int)md;
    if(a < 0){
      a += md;
    }
    return mulR((unsigned)a);
  }
  unsigned reduce(unsigned T){
    unsigned m = T * mdninv;
    unsigned t = (unsigned)((T + (unsigned long long)m*md) >> W);
    if(t >= md){
      t -= md;
    }
    return t;
  }
  unsigned reduce(unsigned long long T){
    unsigned m = (unsigned)T * mdninv;
    unsigned t = (unsigned)((T + (unsigned long long)m*md) >> W);
    if(t >= md){
      t -= md;
    }
    return t;
  }
  unsigned get(){
    return reduce(val);
  }
  mint &operator+=(mint a){
    val += a.val;
    if(val >= md){
      val -= md;
    }
    return *this;
  }
  mint &operator-=(mint a){
    if(val < a.val){
      val = val + md - a.val;
    }
    else{
      val -= a.val;
    }
    return *this;
  }
  mint &operator*=(mint a){
    val = reduce((unsigned long long)val*a.val);
    return *this;
  }
  mint &operator/=(mint a){
    return *this *= a.inverse();
  }
  mint operator+(mint a){
    return mint(*this)+=a;
  }
  mint operator-(mint a){
    return mint(*this)-=a;
  }
  mint operator*(mint a){
    return mint(*this)*=a;
  }
  mint operator/(mint a){
    return mint(*this)/=a;
  }
  mint operator+(int a){
    return mint(*this)+=mint(a);
  }
  mint operator-(int a){
    return mint(*this)-=mint(a);
  }
  mint operator*(int a){
    return mint(*this)*=mint(a);
  }
  mint operator/(int a){
    return mint(*this)/=mint(a);
  }
  mint operator+(long long a){
    return mint(*this)+=mint(a);
  }
  mint operator-(long long a){
    return mint(*this)-=mint(a);
  }
  mint operator*(long long a){
    return mint(*this)*=mint(a);
  }
  mint operator/(long long a){
    return mint(*this)/=mint(a);
  }
  mint operator-(void){
    mint 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();
  }
  mint inverse(){
    int a = val;
    int b = md;
    int u = 1;
    int v = 0;
    int t;
    mint 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 = (unsigned long long)u*RR % md;
    return res;
  }
  mint pw(unsigned long long b){
    mint a(*this);
    mint res;
    res.val = R;
    while(b){
      if(b&1){
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  bool operator==(int a){
    return mulR(a)==val;
  }
  bool operator!=(int a){
    return mulR(a)!=val;
  }
}
;
unsigned mint::md;
unsigned mint::W;
unsigned mint::R;
unsigned mint::Rinv;
unsigned mint::mdninv;
unsigned mint::RR;
mint operator+(int a, mint b){
  return mint(a)+=b;
}
mint operator-(int a, mint b){
  return mint(a)-=b;
}
mint operator*(int a, mint b){
  return mint(a)*=b;
}
mint operator/(int a, mint b){
  return mint(a)/=b;
}
mint operator+(long long a, mint b){
  return mint(a)+=b;
}
mint operator-(long long a, mint b){
  return mint(a)-=b;
}
mint operator*(long long a, mint b){
  return mint(a)*=b;
}
mint operator/(long long a, mint b){
  return mint(a)/=b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class T> struct Matrix{
  int r;
  int c;
  int mem;
  T*dat;
  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;
    int j;
    r = a.r;
    c = a.c;
    j = r * c;
    changeSize(r,c);
    for(i=(0);i<(j);i++){
      dat[i] = a.dat[i];
    }
    return *this;
  }
  Matrix<T>& operator=(const int a){
    int i;
    int 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;
    int 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;
    int 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;
    int j;
    int k;
    int x;
    T*m;
    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;
    int j;
    j = r * c;
    for(i=(0);i<(j);i++){
      dat[i] *= a;
    }
    return *this;
  }
  Matrix<T>& operator*=(const long long a){
    int i;
    int j;
    j = r * c;
    for(i=(0);i<(j);i++){
      dat[i] *= a;
    }
    return *this;
  }
  Matrix<T>& operator*=(const double a){
    int i;
    int 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){
  int i;
  int j;
  Matrix<T> res;
  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 int isPrime_L(T n){
  T i;
  if(n<=1){
    return 0;
  }
  if(n<=3){
    return 1;
  }
  if(n%2==0){
    return 0;
  }
  for(i=3;i*i<=n;i+=2){
    if(n%i==0){
      return 0;
    }
  }
  return 1;
}
template<class T, class S> inline T pow_L(T a, S b){
  T res = 1;
  res = 1;
  for(;;){
    if(b&1){
      res *= a;
    }
    b >>= 1;
    if(b==0){
      break;
    }
    a *= a;
  }
  return res;
}
inline double pow_L(double a, double b){
  return pow(a,b);
}
int N;
int M;
int A[10000];
int B[10000];
long long T;
int em[100][100];
int ok[100];
int main(){
  int RZTsC2BF, i;
  wmem = memarr;
  {
    mint x;
    x.setmod(MD);
  }
  Rand rnd;
  rd(N);
  rd(M);
  rd(T);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(M);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
      rd(B[Lj4PdHRW]);
    }
  }
  for(i=(0);i<(M);i++){
    em[A[i]][B[i]] = 1;
  }
  Matrix<mint> mt(N, N);
  for(RZTsC2BF=(0);RZTsC2BF<(5);RZTsC2BF++){
    int p = rnd.get(1000000000-100000000, 1000000000);
    while(!isPrime_L(p)){
      p++;
    }
    mt[0][0].setmod(p);
    for(i=(0);i<(N);i++){
      int j;
      for(j=(0);j<(N);j++){
        mt[i][j] = em[i][j];
      }
    }
    (mt = pow_L(mt,T));
    for(i=(0);i<(N);i++){
      if(mt[0][i]!=0){
        ok[i] = 1;
      }
    }
  }
  {
    int APIVbQlN;
    int YREPHmFM;
    if(N==0){
      YREPHmFM = 0;
    }
    else{
      YREPHmFM = ok[0];
      for(APIVbQlN=(1);APIVbQlN<(N);APIVbQlN++){
        YREPHmFM += ok[APIVbQlN];
      }
    }
    wt_L(YREPHmFM);
    wt_L('\n');
  }
  return 0;
}
// cLay version 20210103-1 [bug fixed 1]

// --- original code ---
// int N, M, A[1d4], B[1d4]; ll T; int em[100][100];
// int ok[100];
// {
//   Rand rnd;
//   rd(N,M,T,(A,B)(M));
//   rep(i,M) em[A[i]][B[i]] = 1;
//   Matrix<mint> mt(N, N);
// 
//   rep(5){
//     int p = rnd.get(1d9-1d8, 1d9);
//     while(!isPrime(p)) p++;
//     mt[0][0].setmod(p);
//     rep(i,N) rep(j,N) mt[i][j] = em[i][j];
//     mt **= T;
//     rep(i,N) if(mt[0][i]!=0) ok[i] = 1;
//   }
//   wt(sum(ok(N)));
// }