제출 #198114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198114		model_code	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2139 ms	308976 KiB

amusementpark

#include <vector>
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; 
template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
	inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
	/*extended GCD(slow):ll t=0,nt=1,r=N,nr=a;while(nr){ll q=r/nr;t-=q*nt;swap(t,nt);r-=q*nr;swap(r,nr);}assert(r<=1);return(t<0)?t+N:t;*/
	inline ui inv(ui a){return pow(a,N-2);}
public:
    inline Field(int x = 0) : v(x) {}
	inline Field<N> pow(int p){return (*this)^p; }
	inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
    inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
    inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
    inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
    inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
    inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
    inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
    inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
    inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
    inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
    inline bool operator==(const Field<N>&o) const { return o.v==v; }
	inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
	inline explicit operator ui() const { return v; }
	inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
	inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}

typedef Field<998244353> FieldMod;
typedef pair<int,FieldMod> FF;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> E(N, 0), F(N, 0);
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v;
        --u; --v;
        E[u] |= 1<<v;
        F[v] |= 1<<u;
    } 
    
    int g = 1<<N;
    int f = g-1;
    
    vector<vector<FF>> D(g);
    D[0].push_back({f, 1});
    vector<FF> X;
    X.reserve(20000);
    for (int sorted = 0; sorted < g; ++sorted) {
        sort(D[sorted].begin(),D[sorted].end(), [](const FF& a, const FF& b) { return a.x < b.x; });
        for (auto d: D[sorted]) {
            if (X.empty() || X.back().x != d.x) {
                X.push_back(d);
            } else {
                X.back().y += d.y;
            }
        }

        for (auto d : X) {
            int cands = d.x;
            for (int j = 0; j < N; ++j) {
                if (cands&(1<<j)) {
                    int newCands = (cands & (~((1<<(j+1))-1))) | ((E[j]|F[j]) &~sorted);
                    int newSorted = sorted | (1<<j);
                    D[newSorted].push_back({newCands, d.y});
                }
            }
        }
        
        X.clear();
    }

    FieldMod ans = 0;
    for (auto f: D[f]) ans += f.y;
    cout << ans * M / 2 << endl;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37