#905623 (C++17) No.2435 Order All Company

提出ソース

結果

問題	No.2435 Order All Company
ユーザー	hari64
提出日時	2023-08-18 22:23:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	39 ms / 2,000 ms
コード長	13,181 bytes
コンパイル時間	2,734 ms
コンパイル使用メモリ	227,152 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-06 04:37:51
合計ジャッジ時間	4,465 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	37 ms 5,376 KB
testcase_06	AC	37 ms 5,376 KB
testcase_07	AC	24 ms 5,376 KB
testcase_08	AC	38 ms 5,376 KB
testcase_09	AC	39 ms 5,376 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	27 ms 5,376 KB
testcase_15	AC	30 ms 5,376 KB
testcase_16	AC	19 ms 5,376 KB
testcase_17	AC	37 ms 5,376 KB
testcase_18	AC	17 ms 5,376 KB
testcase_19	AC	13 ms 5,376 KB
testcase_20	AC	17 ms 5,376 KB
testcase_21	AC	17 ms 5,376 KB
testcase_22	AC	25 ms 5,376 KB
testcase_23	AC	10 ms 5,376 KB
testcase_24	AC	18 ms 5,376 KB
testcase_25	AC	25 ms 5,376 KB
testcase_26	AC	20 ms 5,376 KB
testcase_27	AC	24 ms 5,376 KB
testcase_28	AC	17 ms 5,376 KB
testcase_29	AC	21 ms 5,376 KB
testcase_30	AC	19 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	3 ms 5,376 KB
testcase_35	AC	5 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef hari64
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#include "util/viewer.hpp"
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
// clang-format off
using namespace std;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vc<T>>;
template <typename T> using vvvc = vector<vvc<T>>;
using ll = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;
using vll = vc<ll>; using vvll = vvc<ll>; using vvvll = vvvc<ll>;
using vb = vc<bool>; using vvb = vvc<bool>; using vvvb = vvvc<bool>;
using vpii = vc<pii>; using vvpii = vvc<pii>; using vpll = vc<pll>; using vvpll = vvc<pll>;
using vtiii = vc<tiii>; using vvtiii = vvc<tiii>; using vtlll = vc<tlll>; using vvtlll = vvc<tlll>;
#define ALL(x) begin(x), end(x)
#define RALL(x) (x).rbegin(), (x).rend()
constexpr int INF = 1001001001; constexpr long long INFll = 1001001001001001001;
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
// clang-format on

// clang-format off
namespace internal{template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T,__int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;
constexpr long long safe_mod(long long x,long long m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m):_m(m),im((unsigned long long)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned long long z=a;z*=b;unsigned long long x=(unsigned long long)(((unsigned __int128)(z)*im)>>64);unsigned int v=(unsigned int)(z-x*_m);if(_m<=v)v+=_m;return v;}};
constexpr long long pow_mod_constexpr(long long x,long long n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned long long r=1;unsigned long long y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr pair<long long,long long>inv_gcd(long long a,long long b){a=safe_mod(a,b);if(a==0)return{b,0};long long s=b,t=a;long long m0=0,m1=1;while(t){long long u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long long d=n-1;while(d%2==0)d/=2;constexpr long long bases[3]={2,7,61};for(long long a:bases){long long t=d;long long y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}template<int n>constexpr bool is_prime=is_prime_constexpr(n);} // namespace internal
template<int m>struct static_modint{using mint=static_modint;static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){long long x=(long long)(v%(long long)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}
mint&operator*=(const mint&rhs){unsigned long long z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&is,mint&rhs){long long v;is>>v;v%=(long long)(umod());if(v<0)v+=umod();;rhs._v=(unsigned int)v;return is;}static constexpr bool prime=internal::is_prime<m>;private:unsigned int _v;static constexpr unsigned int umod(){return m;}};
constexpr int MOD = 998244353;using mint=static_modint<MOD>;vector<mint>mint_factorial={mint(1)};/*n>1e8 ⇒ fast_modfact(deprecated)*/mint modfact(int n){assert(n<=100000000);if(int(mint_factorial.size())<=n){for(int i=mint_factorial.size();i<=n;i++){mint next=mint_factorial.back()*i;mint_factorial.push_back(next);}}return mint_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::mod();if(a.val()==1)return a;if(a.pow((p-1)>>1).val()!=1)return -1;mint b=1,one=1;while(b.pow((p-1)>>1).val()==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=a.pow((m-1)>>1);mint y=a*x*x;x*=a;mint z=b.pow(m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=z.pow(1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*(modfact(k)).inv()*modfact(n-k).inv();}
/*min x s.t. a^x ≡ b (mod M) or -1*/int modlog(mint a,mint b){if(gcd(a.mod(),a.val())!=1){cout<<"\033[1;31mCAUTION: m must be coprime to a.\033[0m"<<endl;assert(false);}long long m=mint::mod();long long sq=round(sqrt(m))+1;unordered_map<long long,long long>ap;mint re=a;for(long long r=1;r<sq;r++){if(ap.find(re.val())==ap.end())ap[re.val()]=r;re*=a;}mint A=a.inv().pow(sq);re=b;for(mint q=0;q.val()<sq;q++){if(re==1&&q!=0)return(q*sq).val();if(ap.find(re.val())!=ap.end())return(q*sq+ap[re.val()]).val();re*=A;}return-1;};
// clang-format on

template <class T>  // clang-format off
struct matrix{
    vector<vector<T>>A;
    static matrix I(int n){matrix mat(n);for(int i=0;i<int(n);i++)mat[i][i]=1;return mat;}
    matrix()=default;
    matrix(vector<vector<T>>&vvec){A=vvec;}
    matrix(int n,int m):A(n,vector<T>(m,0)){}
    matrix(int n,int m,T init):A(n,vector<T>(m,init)){}
    matrix(int n,vector<T>&vec):A(n,vec){}
    matrix(int n):A(n,vector<T>(n,0)){}
    int height()const{return A.size();}
    int width()const{return A[0].size();}
    inline vector<T>&operator[](int k){return A[k];}
    bool operator==(const matrix&B){int n=height(),m=width();if(n!=B.height()or m!=B.width())return false;for(int i=0;i<int(n);i++)for(int j=0;j<int(m);j++)if((*this)[i][j]!=B[i][j])return false;return true;}
    matrix&operator+=(const matrix&B){int n=height(),m=width();assert(n==B.height()&&m==B.width());for(int i=0;i<int(n);i++)for(int j=0;j<int(m);j++)(*this)[i][j]+=B[i][j];return*this;}
    matrix&operator-=(const matrix&B){int n=height(),m=width();assert(n==B.height()&&m==B.width());for(int i=0;i<int(n);i++)for(int j=0;j<int(m);j++)(*this)[i][j]-=B[i][j];return*this;}
    matrix&operator*=(const matrix&B){int n=height(),m=B.width(),p=width();assert(p==B.height());vector<vector<T>>C(n,vector<T>(m,0));for(int i=0;i<int(n);i++)for(int j=0;j<int(m);j++)for(int k=0;k<int(p);k++)C[i][j]+=(*this)[i][k]*B[k][j];A.swap(C);return*this;}
    matrix&operator^=(long long k){matrix B=matrix::I(height());while(k>0){if(k&1)B*=(*this);*this*=*this;k>>=1ll;}A.swap(B.A);return*this;}
    matrix operator+(const matrix&B)const{return(matrix(*this)+=B);}
    matrix operator-(const matrix&B)const{return(matrix(*this)-=B);}
    matrix operator*(const matrix&B)const{return(matrix(*this)*=B);}
    matrix operator^(const long long&k)const{return(matrix(*this)^=k);}
    matrix&operator+=(const T&t){int n=height(),m=width();for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]+=t;return*this;}
    matrix&operator-=(const T&t){int n=height(),m=width();for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]-=t;return*this;}
    matrix&operator*=(const T&t){int n=height(),m=width();for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]*=t;return*this;}
    matrix&operator/=(const T&t){int n=height(),m=width();for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]/=t;return*this;}
    matrix operator+(const T&t)const{return(matrix(*this)+=t);}
    matrix operator-(const T&t)const{return(matrix(*this)-=t);}
    matrix operator*(const T&t)const{return(matrix(*this)*=t);}
    matrix operator/(const T&t)const{return(matrix(*this)/=t);}
    friend ostream&operator<<(ostream&os,matrix&p){int n=p.height(),m=p.width();assert(n>0&&m>0);os<<" (h:"<<p.height()<<", w:"<<p.width()<<")\n";for(int i=0;i<n;i++){os<<'[';for(int j=0;j<m;j++)os<<p[i][j]<<(j==m-1?(i!=n-1?"]\n":"]"):",");}return(os);}
    bool is_binary(){for(int i=0;i<height();i++)for(int j=0;j<width();j++)if(A[i][j]!=0&&A[i][j]!=1)return false;return true;};
    // 行列式
    T determinant(){matrix B(*this);int n=height(),m=width();assert(n==m);T ret=1;for(int i=0;i<n;i++){int idx=-1;for(int j=i;j<n;j++)if(B[j][i]!=0)idx=j;if(idx==-1)return 0;if(i!=idx){ret*=-1;swap(B[i],B[idx]);}ret*=B[i][i];T vv=B[i][i];for(int j=0;j<n;j++)B[i][j]/=vv;for(int j=i+1;j<n;j++){T a=B[j][i];for(int k=0;k<n;k++){B[j][k]-=B[i][k]*a;}}}return ret;}
    // 逆行列 求められない場合は0
    matrix inv(){int n=height();if(determinant()==T(0))return matrix(0);matrix a(*(this)),l=I(n),u(n);for(int j=0;j<n;j++)u[0][j]=a[0][j];for(int j=1;j<n;j++)l[j][0]=a[j][0]/u[0][0];for(int k=1;k<n;k++){for(int j=k;j<n;j++)for(int i=0;i<k;i++)a[j][k]-=l[j][i]*u[i][k];u[k][k]=a[k][k];for(int j=k+1;j<n;j++){u[k][j]=a[k][j];for(int i=0;i<k;i++)u[k][j]-=l[k][i]*u[i][j];}for(int j=k+1;j<n;j++)l[j][k]=a[j][k]/u[k][k];}matrix x(n),y=I(n);for(int i=0;i<n;i++)for(int j=0;j<n;j++){for(int k=0;k<j;k++)y[j][i]-=l[j][k]*y[k][i];}
        T sigma;for(int h=0;h<n;h++)for(int i=n-1;i>=0;i--){sigma=y[i][h];for(int j=i+1;j<n;j++){sigma-=u[i][j]*x[j][h];}x[i][h]=sigma/u[i][i];}return x;}
    // PA==LU Lは下三角(対角成分1) Uは上三角
    tuple<matrix,matrix,matrix>LU_decomposition(){assert(height()==width());int n=height();matrix A(*(this));vector<int>p(n);for(int i=0;i<n;i++)p[i]=i;for(int k=0;k<n-1;k++){T max_a=0;int best_i=-1;for(int i=k;i<n;i++){T absolute=(A[p[i]][k]>=0?A[p[i]][k]:-A[p[i]][k]);if(absolute>=max_a)max_a=absolute,best_i=i;}int i=best_i;swap(p[i],p[k]);T w=T(1)/A[p[k]][k];for(int i=k+1;i<n;i++){A[p[i]][k]*=w;for(int j=k+1;j<n;j++)A[p[i]][j]-=A[p[i]][k]*A[p[k]][j];}}
        matrix L(n),U(n),P(n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){L[i][j]=(i>j?A[p[i]][j]:T(0));U[i][j]=(i<=j?A[p[i]][j]:T(0));}L[i][i]=T(1);P[i][p[i]]=T(1);}return{P,L,U};}
};  // clang-format on

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, K;
    cin >> N >> K;
    vc<vpii> ABs(K);
    for (int i = 0; i < K; i++) {
        int T;
        cin >> T;
        ABs[i].resize(T);
        for (int j = 0; j < T; j++) {
            int A;
            int B;
            cin >> A >> B;
            A--;
            B--;
            ABs[i][j] = {A, B};
        }
    }

    mint ans = 0;
    for (int bit = 0; bit < (1 << K); bit++) {
        matrix<mint> mat(N - 1, N - 1);
        for (int k = 0; k < K; k++) {
            if (bit & (1 << k)) {
                for (auto& [a, b] : ABs[k]) {
                    if (a != N - 1 && b != N - 1) mat[a][b]--;
                    if (a != N - 1 && b != N - 1) mat[b][a]--;
                    if (a != N - 1) mat[a][a]++;
                    if (b != N - 1) mat[b][b]++;
                }
            }
        }

        // cerr << mat << endl;

        debug(mat.determinant());

        ans += mat.determinant() * int(pow(-1, K - __builtin_popcount(bit)));
    }

    debug(ans);

    cout << ans << endl;

    return 0;
}

yukicoder

結果

テストケース

ソースコード