結果

問題 No.2825 Sum of Scores of Sets of Specified Sections
コンテスト
ユーザー Taiki0715
提出日時 2024-07-27 14:37:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 90 ms / 3,000 ms
コード長 6,251 bytes
コンパイル時間 5,784 ms
コンパイル使用メモリ 317,840 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-27 14:38:01
合計ジャッジ時間 7,536 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}
istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}
#endif
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define esper(...) static_cast<void>(0)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define reps(i,a,n) for(int i=(a);i<int(n);i++)
#define rep(i,n) reps(i,0,n)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<x<<'\n',static_cast<void>(0)
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
void SOLVE();
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(16);
  #ifdef LOCAL
  clock_t start=clock();
  #endif
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
  #ifdef LOCAL
  cerr<<"time:";
  cerr<<(clock()-start)/1000;
  cerr<<"ms\n";
  #endif
}
template<typename T>
vector<vector<T>>matrix_mul(const vector<vector<T>>&a,const vector<vector<T>>&b){
  assert(a[0].size()==b.size());
  vector<vector<T>>ret(a.size(),vector<T>(b[0].size(),0));
  rep(i,a.size())rep(j,b.size())rep(k,b[0].size())ret[i][k]+=a[i][j]*b[j][k];
  return ret;
}
template<typename T>
vector<vector<T>>matrix_pow(vector<vector<T>>a,ll k){
  assert(a.size()==a[0].size());
  vector<vector<T>>ret(a.size(),vector<T>(a.size(),0));
  rep(i,a.size())ret[i][i]=1;
  while(k){
    if(k&1)ret=matrix_mul(ret,a);
    a=matrix_mul(a,a);
    k>>=1;
  }
  return ret;
}
template<typename T>
T matrix_det(vector<vector<T>>a){
  if(a.empty())return 1;
  assert(a.size()==a[0].size());
  int n=a.size();
  T ret=1;
  rep(i,n){
    int id=-1;
    reps(j,i,n){
      if(a[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1)return 0;
    if(i!=id){
      ret*=-1;
      swap(a[i],a[id]);
    }
    ret*=a[i][i];
    T inv=a[i][i].inv();
    rep(j,n)a[i][j]*=inv;
    reps(j,i+1,n){
      T x=a[j][i];
      rep(k,n)a[j][k]-=a[i][k]*x;
    }
  }
  return ret;
}
template<typename T>
vector<vector<T>>matrix_inv(vector<vector<T>>a){
  assert(a.size()==a[0].size());
  int n=a.size();
  vector<vector<T>>ret(n,vector<T>(n,0));
  rep(i,n)ret[i][i]=1;
  rep(i,n){
    int id=-1;
    reps(j,i,n){
      if(a[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1)return vector<vector<T>>(n,vector<T>(n,0));
    if(i!=id){
      swap(a[i],a[id]);
      swap(ret[i],ret[id]);
    }
    T inv=a[i][i].inv();
    rep(j,n){
      a[i][j]*=inv;
      ret[i][j]*=inv;
    }
    rep(j,n)if(i!=j){
      T x=a[j][i];
      rep(k,n){
        a[j][k]-=a[i][k]*x;
        ret[j][k]-=ret[i][k]*x;
      }
    }
  }
  return ret;
}
template<typename T>
void matrix_hessenberg(vector<vector<T>>&a){
  assert(a.size()==a[0].size());
  int n=a.size();
  rep(i,n-2){
    int id=-1;
    reps(j,i+1,n){
      if(a[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1)continue;
    swap(a[i+1],a[id]);
    rep(j,n)swap(a[j][i+1],a[j][id]);
    T inv=a[i+1][i].inv();
    reps(j,i+2,n){
      T x=a[j][i]*inv;
      rep(k,n)a[j][k]-=a[i+1][k]*x;
      rep(k,n)a[k][i+1]+=a[k][j]*x;
    }
  }
}
//det(xI-a)
template<typename T>
vector<T>matrix_charpoly(vector<vector<T>>a){
  matrix_hessenberg(a);
  int n=a.size();
  vector<vector<T>>ret(n+1);
  ret[0]={1};
  rep(i,n){
    ret[i+1].resize(i+2,0);
    rep(j,i+1)ret[i+1][j+1]+=ret[i][j];
    rep(j,i+1)ret[i+1][j]-=ret[i][j]*a[i][i];
    T b=1;
    for(int j=i-1;j>=0;j--){
      b*=a[j+1][j];
      T c=-a[j][i]*b;
      rep(k,j+1)ret[i+1][k]+=c*ret[j][k];
    }
  }
  return ret[n];
}
//det(a+xb)
template<typename T>
vector<T>matrix_detpoly(vector<vector<T>>a,vector<vector<T>>b){
  assert(a.size()==a[0].size());
  assert(b.size()==b[0].size());
  assert(a.size()==b.size());
  int n=a.size();
  int cx=0;
  T ab=1;
  rep(i,n){
    int id=-1;
    reps(j,i,n){
      if(b[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1){
      if(++cx>n)return vector<T>(n+1,0);
      rep(j,n){
        T v=b[j][i];
        b[j][i]=0;
        rep(k,n)a[k][i]-=v*a[k][j];
      }
      rep(j,n)swap(a[j][i],b[j][i]);
      i--;
      continue;
    }
    if(i!=id){
      swap(a[i],a[id]);
      swap(b[i],b[id]);
      ab*=-1;
    }
    ab*=b[i][i];
    T inv=b[i][i].inv();
    rep(j,n){
      a[i][j]*=inv;
      b[i][j]*=inv;
    }
    rep(j,n)if(i!=j){
      T v=b[j][i];
      rep(k,n){
        a[j][k]-=a[i][k]*v;
        b[j][k]-=b[i][k]*v;
      }
    }
  }
  rep(i,n)rep(j,n)a[i][j]*=-1;
  vector<T> poly=matrix_charpoly(a);
  rep(i,n+1)poly[i]*=ab;
  poly.erase(poly.begin(),poly.begin()+cx);
  poly.resize(n+1,0);
  return poly;
}
using mint=modint998244353;
void SOLVE(){
  int h,w;
  cin>>h>>w;
  vector<vector<mint>>a(h,vector<mint>(w)),b(h,vector<mint>(w));
  cin>>a>>b;
  vector<vector<mint>>c(w,vector<mint>(h));
  rep(i,h)rep(j,w)c[j][i]=b[i][j];
  a=matrix_mul(a,c);
  rep(i,a.size())a[i][i]++;
  cout<<(matrix_det(a)-1).val()<<endl;
}
0