QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#853745#7. 主旋律Starrykiller100 ✓868ms3888kbC++207.1kb2025-01-11 18:52:042025-01-11 18:52:05

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 18:52:05]
  • 评测
  • 测评结果：100
  • 用时：868ms
  • 内存：3888kb
查看
  • [2025-01-11 18:52:04]
  • 提交

answer

// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;

_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }

namespace sk {
    // modint: https://www.cnblogs.com/hzy1/p/16344746.html
    // Edited by Starrykiller.
    using i64=int64_t;
    using i128=__int128;
    using u128=unsigned __int128;
    using u64=uint64_t;
    using i32=int32_t;
    using u32=uint32_t;
    struct barrett { // From Atcoder Library.
        u32 _m;
        u64 im;
        explicit barrett(u32 m) : _m(m), im((u64)(-1)/m+1) {}
        u32 umod() const { return _m; }
        u32 mul(u32 a, u32 b) const {
            u64 z=a; z*=b;
            u64 x=(u64)((u128(z)*im) >> 64);
            u64 y = x * _m;
            return (u32)(z-y+(z<y?_m:0));
        }
    };
    constexpr i32 inverse(i32 a, i32 m) { i32 r=1;
        while (a>1) { i32 t=m/a; r=i64(r)*(m-t)%m; a=m-t*a; }
        return r;
    }
    template<i32 p>
    struct static_modint { 
        using mi=static_modint;
        public:
        constexpr static_modint(i64 x) : x(normal(x%p)) {}
        constexpr static_modint(i32 x, std::nullptr_t) : x(x) {}
        constexpr static_modint(): x(0) {}
        constexpr i32 normal(i32 x) { 
            if (x>=p) x-=p;
            return x+((x>>31)&p); 
        }
        constexpr i32 val() const { return x; }
        constexpr static i32 mod() { return p; }
        constexpr explicit operator bool() const { return x; }
        constexpr mi inv() const { assert(x!=0); return mi(inverse(x,p),nullptr); }
        constexpr mi pow(i64 x) const { assert(x>=0); mi a=*this, res=1;
            while (x) { if (x&1) res*=a; a*=a; x>>=1; } return res; }
        constexpr mi operator-() const { return mi(p-x); }
        constexpr mi& operator+=(const mi &rhs) { x=normal(x+rhs.x); return *this; }
        constexpr mi& operator-=(const mi &rhs) { x=normal(x-rhs.x); return *this; }
        constexpr mi& operator++() { return (*this)+=1; }
        constexpr mi& operator--() { return (*this)-=1; }
        constexpr mi& operator*=(const mi &rhs) { x=i64(x)*rhs.x%p; return *this; }
        constexpr mi& operator/=(const mi &rhs) { return *this *= rhs.inv(); }
        constexpr friend mi operator+(const mi &lhs, const mi &rhs) { auto res=lhs; res+=rhs; return res; }
        constexpr friend mi operator-(const mi &lhs, const mi &rhs) { auto res=lhs; res-=rhs; return res; }
        constexpr friend mi operator*(const mi &lhs, const mi &rhs) { auto res=lhs; res*=rhs; return res; }
        constexpr friend mi operator/(const mi &lhs, const mi &rhs) { auto res=lhs; res/=rhs; return res; }
        constexpr friend mi operator++(mi &x, i32) { auto tmp=x; x+=1; return tmp; }
        constexpr friend mi operator--(mi &x, i32) { auto tmp=x; x-=1; return tmp; }
        constexpr friend std::istream& operator>>(std::istream &is, mi &a) { i64 v; is>>v; a=v; return is; }
        constexpr friend std::ostream& operator<<(std::ostream &os, const mi &a) { os<<a.val(); return os; }
        constexpr bool operator==(const mi& rhs) const { return val()==rhs.val(); }
        constexpr bool operator!=(const mi& rhs) const { return val()!=rhs.val(); }
        private:
        i32 x;
    };
    template<i32 id>
    struct dynamic_modint { 
        using mi=dynamic_modint;
        public:
        constexpr dynamic_modint(i64 x) : x(normal(x%mod())) {}
        constexpr dynamic_modint(i32 x, std::nullptr_t) : x(x) {}
        constexpr dynamic_modint(): x(0) {}
        constexpr i32 normal(i32 x) { 
            auto p=mod();
            if (x>=p) x-=p;
            return x+((x>>31)&p); 
        }
        constexpr i32 val() const { return x; }
        constexpr static void set_mod(i32 m) { assert(m>=1); bt=barrett((u32)m); }
        constexpr static i32 mod() { return bt.umod(); }
        constexpr explicit operator bool() const { return x; }
        constexpr mi inv() const { assert(x!=0); return mi(inverse(x,mod()),nullptr); }
        constexpr mi pow(i64 x) const { assert(x>=0); mi a=*this, res=1;
            while (x) { if (x&1) res*=a; a*=a; x>>=1; } return res; }
        constexpr mi operator-() const { return mi(mod()-x); }
        constexpr mi& operator+=(const mi &rhs) { x=normal(x+rhs.x); return *this; }
        constexpr mi& operator-=(const mi &rhs) { x=normal(x-rhs.x); return *this; }
        constexpr mi& operator++() { return (*this)+=1; }
        constexpr mi& operator--() { return (*this)-=1; }
        constexpr mi& operator*=(const mi &rhs) { x=bt.mul(val(),rhs.val()); return *this; }
        constexpr mi& operator/=(const mi &rhs) { return *this *= rhs.inv(); }
        constexpr friend mi operator+(const mi &lhs, const mi &rhs) { auto res=lhs; res+=rhs; return res; }
        constexpr friend mi operator-(const mi &lhs, const mi &rhs) { auto res=lhs; res-=rhs; return res; }
        constexpr friend mi operator*(const mi &lhs, const mi &rhs) { auto res=lhs; res*=rhs; return res; }
        constexpr friend mi operator/(const mi &lhs, const mi &rhs) { auto res=lhs; res/=rhs; return res; }
        constexpr friend mi operator++(mi &x, i32) { auto tmp=x; x+=1; return tmp; }
        constexpr friend mi operator--(mi &x, i32) { auto tmp=x; x-=1; return tmp; }
        constexpr friend std::istream& operator>>(std::istream &is, mi &a) { i64 v; is>>v; a=v; return is; }
        constexpr friend std::ostream& operator<<(std::ostream &os, const mi &a) { os<<a.val(); return os; }
        constexpr bool operator==(const mi& rhs) const { return val()==rhs.val(); }
        constexpr bool operator!=(const mi& rhs) const { return val()!=rhs.val(); }
        private:
        i32 x; 
        static barrett bt;
    };
    template<i32 id> barrett dynamic_modint<id>::bt(998244353);
    using modint998244353=static_modint<998244353>;
    using modint1000000007=static_modint<1000000007>;
    using mint=dynamic_modint<-1>; 
};

using ll=sk::modint1000000007;

using u32=uint32_t;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
// int T; cin>>T;
int T=1;
while (T--) []{
    int n, m; cin>>n>>m;
    vector<int> E(1<<n), all(1<<n); 
    auto cnt=[&](u32 s, u32 t) {
        int ans=0;
        for (auto i: range(0,n)) if (s>>i&1) ans+=popcount(E[i]&t);
        return ans;
    };
    for (int u,v; auto _: range(0,m)) {
        cin>>u>>v; E[--u]|=1<<(--v);
    }
    vector<ll> g(1<<n), h(1<<n);
    vector<int> c(1<<n);
    vector<ll> pow(n*n); pow[0]=1;
    for (auto i: range(1u,size(pow))) pow[i]=pow[i-1]*2;
    for (auto s: range(1u,1u<<n)) {
        c[s]=cnt(s,s);
        auto lowbit=s&(-s);
        for (auto t=(s-1)&s; t; t=(t-1)&s) if (t&lowbit)
            h[s]-=g[t]*h[s^t];
        g[s]=pow[c[s]];
        for (auto t=s; t; t=(t-1)&s) {
            g[s]-=pow[cnt(t,s^t)+c[s-t,s-t]]*h[t];
            if (!t) break;
        }
        h[s]+=g[s]; 
    }

    cout<<g.back()<<'\n';
}();
}
源文件, 语言: C++20

详细


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

5 15
4 3
4 2
2 5
2 1
1 2
5 1
3 2
4 1
1 4
5 4
3 4
5 3
2 3
1 5
3 1

output:

9390

result:

ok single line: '9390'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3796kb

input:

5 18
4 3
4 2
2 5
2 1
1 2
5 1
3 2
4 1
1 4
5 4
3 4
5 3
2 3
1 5
3 1
1 3
5 2
2 4

output:

100460

result:

ok single line: '100460'

Test #3:

score: 10
Accepted
time: 1ms
memory: 3640kb

input:

8 35
5 1
8 7
7 8
7 6
6 1
2 5
6 5
8 2
7 2
7 5
3 1
6 3
2 3
5 2
8 5
8 3
6 8
2 1
1 6
2 6
7 3
2 4
3 5
3 2
3 7
7 1
8 4
3 4
3 6
6 4
2 7
4 6
6 7
7 4
8 1

output:

299463717

result:

ok single line: '299463717'

Test #4:

score: 10
Accepted
time: 1ms
memory: 3576kb

input:

8 40
5 1
8 7
7 8
7 6
6 1
2 5
6 5
8 2
7 2
7 5
3 1
6 3
2 3
5 2
8 5
8 3
6 8
2 1
1 6
2 6
7 3
2 4
3 5
3 2
3 7
7 1
8 4
3 4
3 6
6 4
2 7
4 6
6 7
7 4
8 1
1 2
4 8
5 8
4 3
5 7

output:

21156439

result:

ok single line: '21156439'

Test #5:

score: 10
Accepted
time: 1ms
memory: 3800kb

input:

8 45
5 1
8 7
7 8
7 6
6 1
2 5
6 5
8 2
7 2
7 5
3 1
6 3
2 3
5 2
8 5
8 3
6 8
2 1
1 6
2 6
7 3
2 4
3 5
3 2
3 7
7 1
8 4
3 4
3 6
6 4
2 7
4 6
6 7
7 4
8 1
1 2
4 8
5 8
4 3
5 7
2 8
1 5
3 8
1 3
4 1

output:

426670664

result:

ok single line: '426670664'

Test #6:

score: 10
Accepted
time: 3ms
memory: 3888kb

input:

10 65
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9

output:

931896041

result:

ok single line: '931896041'

Test #7:

score: 10
Accepted
time: 0ms
memory: 3544kb

input:

10 70
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 6

output:

303656759

result:

ok single line: '303656759'

Test #8:

score: 10
Accepted
time: 860ms
memory: 3844kb

input:

15 130
7 10
9 12
4 6
1 10
14 9
4 8
8 9
4 3
15 9
3 9
1 8
2 15
8 4
13 7
3 5
14 13
6 2
14 6
8 3
4 2
8 13
9 2
6 13
12 11
6 4
11 8
15 5
3 8
10 8
15 7
15 6
12 15
8 12
13 9
12 9
8 15
11 6
6 7
10 4
2 8
11 12
7 9
7 12
14 1
5 8
10 9
3 7
7 13
11 9
11 10
1 5
1 3
2 1
2 7
10 1
10 15
7 14
5 6
6 1
15 10
5 15
15 8
5...

output:

717458968

result:

ok single line: '717458968'

Test #9:

score: 10
Accepted
time: 868ms
memory: 3840kb

input:

15 140
7 10
9 12
4 6
1 10
14 9
4 8
8 9
4 3
15 9
3 9
1 8
2 15
8 4
13 7
3 5
14 13
6 2
14 6
8 3
4 2
8 13
9 2
6 13
12 11
6 4
11 8
15 5
3 8
10 8
15 7
15 6
12 15
8 12
13 9
12 9
8 15
11 6
6 7
10 4
2 8
11 12
7 9
7 12
14 1
5 8
10 9
3 7
7 13
11 9
11 10
1 5
1 3
2 1
2 7
10 1
10 15
7 14
5 6
6 1
15 10
5 15
15 8
5...

output:

459157220

result:

ok single line: '459157220'

Test #10:

score: 10
Accepted
time: 860ms
memory: 3856kb

input:

15 150
7 10
9 12
4 6
1 10
14 9
4 8
8 9
4 3
15 9
3 9
1 8
2 15
8 4
13 7
3 5
14 13
6 2
14 6
8 3
4 2
8 13
9 2
6 13
12 11
6 4
11 8
15 5
3 8
10 8
15 7
15 6
12 15
8 12
13 9
12 9
8 15
11 6
6 7
10 4
2 8
11 12
7 9
7 12
14 1
5 8
10 9
3 7
7 13
11 9
11 10
1 5
1 3
2 1
2 7
10 1
10 15
7 14
5 6
6 1
15 10
5 15
15 8
5...

output:

663282473

result:

ok single line: '663282473'
English 繁體中文 简体中文

服务器时间: 2025-01-20 07:16:31 | 开源项目