#1030176 (C++17) No.2985 May Count Induced C4 Subgraphs

提出ソース
結果

問題	No.2985 May Count Induced C4 Subgraphs
ユーザー	👑 Nachia
提出日時	2024-12-06 03:55:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,433 ms / 5,000 ms
コード長	15,530 bytes
コンパイル時間	2,051 ms
コンパイル使用メモリ	113,460 KB
実行使用メモリ	24,784 KB
最終ジャッジ日時	2024-12-07 07:10:50
合計ジャッジ時間	15,675 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
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,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	1,390 ms 24,660 KB
testcase_07	AC	1,433 ms 24,664 KB
testcase_08	AC	1,391 ms 24,664 KB
testcase_09	AC	1,351 ms 24,660 KB
testcase_10	AC	1,404 ms 24,660 KB
testcase_11	AC	1,399 ms 24,660 KB
testcase_12	AC	166 ms 24,660 KB
testcase_13	AC	173 ms 24,660 KB
testcase_14	AC	171 ms 24,656 KB
testcase_15	AC	167 ms 24,660 KB
testcase_16	AC	165 ms 24,660 KB
testcase_17	AC	596 ms 24,660 KB
testcase_18	AC	623 ms 24,660 KB
testcase_19	AC	602 ms 24,660 KB
testcase_20	AC	583 ms 24,784 KB
testcase_21	AC	618 ms 24,636 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include <utility>
#include <cassert>

namespace nachia{

template<class Elem>
class CsrArray{
public:
    struct ListRange{
        using iterator = typename std::vector<Elem>::iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        Elem& operator[](int i) const { return begi[i]; }
    };
    struct ConstListRange{
        using iterator = typename std::vector<Elem>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const Elem& operator[](int i) const { return begi[i]; }
    };
private:
    int m_n;
    std::vector<Elem> m_list;
    std::vector<int> m_pos;
public:
    CsrArray() : m_n(0), m_list(), m_pos() {}
    static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
        CsrArray res;
        res.m_n = n;
        std::vector<int> buf(n+1, 0);
        for(auto& [u,v] : items){ ++buf[u]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.m_list.resize(buf[n]);
        for(int i=(int)items.size()-1; i>=0; i--){
            res.m_list[--buf[items[i].first]] = std::move(items[i].second);
        }
        res.m_pos = std::move(buf);
        return res;
    }
    static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
        CsrArray res;
        res.m_n = pos.size() - 1;
        res.m_list = std::move(list);
        res.m_pos = std::move(pos);
        return res;
    }
    ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    int size() const { return m_n; }
    int fullSize() const { return (int)m_list.size(); }
};

} // namespace nachia

namespace nachia{


struct Graph {
public:
    struct Edge{
        int from, to;
        void reverse(){ std::swap(from, to); }
        int xorval() const { return from ^ to; }
    };
    Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {}
    Graph(int n, const std::vector<std::pair<int, int>>& edges, int undirected = false) : m_n(n), m_isUndir(undirected){
        m_e.resize(edges.size());
        for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second };
    }
    template<class Cin>
    static Graph Input(Cin& cin, int n, bool undirected, int m, int offset = 0){
        Graph res(n, undirected, m);
        for(int i=0; i<m; i++){
            int u, v; cin >> u >> v;
            res[i].from = u - offset;
            res[i].to = v - offset;
        }
        return res;
    }
    int numVertices() const noexcept { return m_n; }
    int numEdges() const noexcept { return int(m_e.size()); }
    int addNode() noexcept { return m_n++; }
    int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; }
    Edge& operator[](int ei) noexcept { return m_e[ei]; }
    const Edge& operator[](int ei) const noexcept { return m_e[ei]; }
    Edge& at(int ei) { return m_e.at(ei); }
    const Edge& at(int ei) const { return m_e.at(ei); }
    auto begin(){ return m_e.begin(); }
    auto end(){ return m_e.end(); }
    auto begin() const { return m_e.begin(); }
    auto end() const { return m_e.end(); }
    bool isUndirected() const noexcept { return m_isUndir; }
    void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); }
    void contract(int newV, const std::vector<int>& mapping){
        assert(numVertices() == int(mapping.size()));
        for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV);
        for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; }
        m_n = newV;
    }
    std::vector<Graph> induce(int num, const std::vector<int>& mapping) const {
        int n = numVertices();
        assert(n == int(mapping.size()));
        for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num);
        std::vector<int> indexV(n), newV(num);
        for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++;
        std::vector<Graph> res; res.reserve(num);
        for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected());
        for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]);
        return res;
    }
    CsrArray<int> getEdgeIndexArray(bool undirected) const {
        std::vector<std::pair<int, int>> src;
        src.reserve(numEdges() * (undirected ? 2 : 1));
        for(int i=0; i<numEdges(); i++){
            auto e = operator[](i);
            src.emplace_back(e.from, i);
            if(undirected) src.emplace_back(e.to, i);
        }
        return CsrArray<int>::Construct(numVertices(), src);
    }
    CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); }
    CsrArray<int> getAdjacencyArray(bool undirected) const {
        std::vector<std::pair<int, int>> src;
        src.reserve(numEdges() * (undirected ? 2 : 1));
        for(auto e : m_e){
            src.emplace_back(e.from, e.to);
            if(undirected) src.emplace_back(e.to, e.from);
        }
        return CsrArray<int>::Construct(numVertices(), src);
    }
    CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); }
private:
    int m_n;
    std::vector<Edge> m_e;
    bool m_isUndir;
};

} // namespace nachia


namespace nachia{

// simple graph
// for each edge
// O( n + m sqrt(m) ) time
template<class Weight>
std::vector<Weight> CountC4Simple(
    int n,
    Graph g,
    std::vector<Weight> W
){
    int m = int(W.size());
    
    // less incident edges, smaller index
    std::vector<int> deg(n);
    for(auto [u,v] : g){ deg[u]++; deg[v]++; }
    std::vector<int> I(n); for(int i=0; i<n; i++) I[i] = i;
    std::sort(I.begin(), I.end(), [&](int l, int r){ return deg[l] < deg[r]; });
    {
        std::vector<int> O(n);
        for(int i=0; i<n; i++) O[I[i]] = i;
        for(auto& [u,v] : g){ u = O[u], v = O[v]; }
    }

    for(auto& e : g) if(e.from < e.to) e.reverse();
    
    // adjacency list

    std::vector<int> estart(n);
    for(int i=0; i<n-1; i++) estart[i+1] = estart[i] + deg[I[i]];
    std::vector<int> eend = estart;
    std::vector<int> eid(m*2);
    std::vector<int> eto(m*2);

    for(int e=0; e<m; e++){
        auto [v,w] = g[e];
        eid[eend[v]] = e;
        eto[eend[v]] = w;
        eend[v]++;
    }
    std::vector<int> eendx = eend;
    for(int v=0; v<n; v++){
        for(int i=estart[v]; i<eendx[v]; i++){
            int e = eid[i];
            int w = eto[i];
            eid[eend[w]] = e;
            eto[eend[w]] = v;
            eend[w]++;
        }
    }
    
    std::vector<Weight> c(n); // c[x] : number of paths(v --> w --> x)
    std::vector<Weight> ans(m);
    for(int v=n-1; v>=0; v--){
        for(int i=estart[v]; i<eend[v]; i++){
            int evw = eid[i];
            int w = eto[i];
            eend[w] -= 1; // remove w -> v
            for(int j=estart[w]; j<eend[w]; j++){
                int ewx = eid[j];
                int x = eto[j];
                c[x] += W[evw] * W[ewx];
            }
        }
        for(int i=estart[v]; i<eend[v]; i++){
            int evw = eid[i];
            int w = eto[i];
            for(int j=estart[w]; j<eend[w]; j++){
                int ewx = eid[j];
                int x = eto[j];
                Weight val = c[x] - W[evw] * W[ewx];
                ans[evw] += val * W[ewx];
                ans[ewx] += val * W[evw];
            }
        }
        for(int i=estart[v]; i<eend[v]; i++){
            int w = eto[i];
            for(int j=estart[w]; j<eend[w]; j++) c[eto[j]] = 0;
        }
    }
    return ans;
}

// for each edge
// O( n + m sqrt(m) ) time
template<class Weight>
std::vector<Weight> CountC4(
    int n,
    Graph g,
    std::vector<Weight> W
){
    int m = int(W.size());
    for(auto& e : g) if(e.to < e.from) e.reverse();
    std::vector<int> I(m);
    for(int i=0; i<m; i++) I[i] = i;
    std::sort(I.begin(), I.end(), [&](int l, int r){
        return g[l].from != g[r].from ? g[l].from < g[r].from : g[l].to < g[r].to;
    });

    std::vector<int> Q(m);
    Graph g2;
    int g2sz = 0;
    std::vector<Weight> W2;
    for(auto e : I){
        if(g2sz == 0 || g2[g2sz-1].from != g[e].from || g2[g2sz-1].to != g[e].to){
            g2.addEdge(g[e].from, g[e].to);
            W2.push_back(0);
            g2sz++;
        }
        W2.back() += W[e];
        Q[e] = g2sz-1;
    }

    auto simple_res = CountC4Simple<Weight>(n, std::move(g2), std::move(W2));
    std::vector<Weight> ans(m);
    for(int e=0; e<m; e++) ans[e] = simple_res[Q[e]];
    return ans;
}

} // namespace nachia

namespace nachia{

// void query(int a, int b, int c);
template<class F>
void EnumerateTriangles(Graph G, F query){
    int n = G.numVertices();
    std::vector<int> C(n);
    for(auto e : G){ C[e.from]++; C[e.to]++; }
    for(auto& e : G) if(std::make_pair(C[e.from],e.from) > std::make_pair(C[e.to],e.to)) e.reverse();
    auto adj = G.getAdjacencyArray(false);
    std::fill(C.begin(), C.end(), n);
    for(int i=0; i<n; i++) if(adj[i].size()){
        for(int e : adj[i]) C[e] = i;
        for(int e : adj[i]) for(int ee : adj[e]) if(C[ee] == i) query(i,e,ee);
    }
}

// void query(int e1, int e2, int e3);
template<class F>
void EnumerateTrianglesForEdge(Graph G, F query){
    int n = G.numVertices();
    std::vector<int> C(n);
    for(auto e : G){ C[e.from]++; C[e.to]++; }
    for(auto& e : G) if(std::make_pair(C[e.from],e.from) > std::make_pair(C[e.to],e.to)) e.reverse();
    auto adj = G.getEdgeIndexArray(false);
    std::fill(C.begin(), C.end(), -1);
    for(int x=0; x<n; x++) if(adj[x].size()){
        for(int e : adj[x]) C[G[e].to] = e;
        for(int e : adj[x]){
            int y = G[e].to;
            for(int ee : adj[y]){
                int z = G[ee].to;
                if(C[z] >= 0) query(e, ee, C[z]);
            }
        }
        for(int e : adj[x]) C[G[e].to] = -1;
    }
}

} // namespace nachia

namespace nachia {

template<class Int>
std::vector<Int> InducedSize4SubgraphCounter2(nachia::Graph g){
    int n = g.numVertices();
    int m = g.numEdges();
    std::vector<int> deg(n, 0);
    for(auto [u,v] : g){ deg[u]++; deg[v]++; }
    std::vector<int> c3_foredge(m, 0);
    nachia::EnumerateTrianglesForEdge(g, [&](int e1, int e2, int e3){
        c3_foredge[e1]++;
        c3_foredge[e2]++;
        c3_foredge[e3]++;
    });
    Int c3 = 0; for(int a : c3_foredge){ c3 += a; } c3 /= 3;
    std::vector<Int> c4_foredge = nachia::CountC4(n, g, std::vector<Int>(m, Int(1)));
    Int c4 = 0; for(Int a : c4_foredge){ c4 += a; } c4 /= 4;

    Int degC2 = 0; for(auto a : deg){ degC2 += Int(a) * (a-1) / 2; }
    Int degC3 = 0; for(auto a : deg){ degC3 += Int(a) * (a-1) * (a-2) / 6; }
    Int adjD = 0; for(auto [u,v] : g){ adjD += Int(deg[u] - 1) * (deg[v] - 1); }
    Int triC2 = 0; for(auto a : c3_foredge){ triC2 += Int(a) * (a-1) / 2;  }
    Int triE = 0;
    for(int i=0; i<m; i++){
        auto [u,v] = g[i];
        triE += c3_foredge[i] * (deg[u] - 2);
        triE += c3_foredge[i] * (deg[v] - 2);
    } triE /= 2;

    std::vector<Int> ans(10);
    ans[0] = Int(n) * (n-1) * (n-2) * (n-3) / 24;
    ans[1] = Int(m) * (n-2) * (n-3) / 2;
    ans[2] = degC2 * (n-3);
    ans[3] = Int(m) * (m-1) / 2 - degC2;
    ans[4] = degC3;
    ans[5] = adjD - c3 * 3;
    ans[6] = c3 * (n-3);
    ans[7] = c4;
    ans[8] = triE;
    ans[9] = triC2;
    return ans;
}

} // namespace nachia

namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const noexcept { return x; }
    my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; }
    my_type pow(unsigned long long i) const noexcept {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const noexcept { return x; }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia

using namespace std;

using Modint = nachia::StaticModint<998244353>;
pair<Modint, Modint> solve(nachia::Graph g){

    Modint tab[10][11] = {
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 0, 1, 2, 2, 3, 3, 3, 4, 4, 5, 6 },
        { 0, 0, 1, 0, 3, 2, 3, 4, 5, 8, 12 },
        { 0, 0, 0, 1, 0, 1, 0, 2, 1, 2, 3 },
        { 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 4 },
        { 0, 0, 0, 0, 0, 1, 0, 4, 2, 6, 12 },
        { 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 4 },
        { 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 12 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6 }
    };

    Modint coeff[11] = { 1, 0, 0, 0, 0, 0, 0, -Modint(3).inv(), 0, 0, 0 };
    Modint xcoeff[11] = { 1, 0, 0, 0, 0, 0, 0, -Modint(3).inv(), 0, 0, 0 };
    for(int i=0; i<10; i++){
        for(int j=i+1; j<10; j++) xcoeff[j] -= xcoeff[i] * tab[i][j];
    }
    
    auto res = nachia::InducedSize4SubgraphCounter2<Modint>(g);
    Modint ans = 0;
    for(int t=0; t<10; t++) ans += res[t] * xcoeff[t];
    return { coeff[7] , ans };
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int N, M; cin >> N >> M;
    auto graph = nachia::Graph::Input(cin, N, true, M, 1);
    auto [T, ans] = solve(graph);
    
    cout << T.val() << " " << ans.val() << "\n";
    return 0;
}
yukicoder

結果

テストケース

ソースコード
