QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847132#7. 主旋律definieren100 ✓100ms5892kbC++208.3kb2025-01-07 17:38:582025-01-07 17:38:59

Judging History

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

  • [2025-01-07 17:38:59]
  • 评测
  • 测评结果：100
  • 用时：100ms
  • 内存：5892kb
查看
  • [2025-01-07 17:38:58]
  • 提交

answer

#include <bits/stdc++.h>

#define fir first
#define sec second
#define mkp make_pair
#define mkt make_tuple
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n'
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n'
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define dbg(x) void()
#define dpi(x, y) void()
#define dbgf(fmt, args...) void()
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ldb = long double;
using i128 = __int128_t;
using ui128 = __uint128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;

namespace {
bool Mbe;
constexpr int MOD = 1e9 + 7;
template<typename T> T Norm(T a, T p = MOD) { return (a % p + p) % p; }
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }
template<typename T> T DivFloor(T a, T b) { return a >= 0 ? a / b : (a - b + 1) / b; }
template<typename T> T DivCeil(T a, T b) { return a >= 0 ? (a + b - 1) / b : a / b; }

namespace FastIO {
	constexpr int LEN = 1 << 20;
	char in[LEN + 1], out[LEN + 1];
	char *pin = in, *pout = out, *ein = in, *eout = out + LEN;

	char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
	void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
	struct Flush { ~Flush() { fwrite(out, 1, pout - out, stdout); pout = out; return; } } _flush;

	template<typename T> T Read() {
		T x = 0; int f = 1; char ch = gc();
		while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return x * f;
	}
	void Read(char *s) {
		char ch = gc();
		while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = gc();
		while ((ch != EOF) && !(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')) *s = ch, s ++, ch = gc();
		*s = '\0'; return;
	}
	template<typename T> void Read(T &x) { x = Read<T>(); return; }
	template<typename T, typename ...Args>
	void Read(T &x, Args &...args) { Read(x), Read(args...); return; }
	template<typename T> void Write(T x) {
		static char stk[40]; int tp = 0;
		if (x < 0) pc('-'), x = ~x + 1;
		do stk[tp++] = x % 10 + 48, x /= 10; while (x);
		while (tp --) pc(stk[tp]);
		return;
	}
	void Write(char ch) { pc(ch); return; }
	void Write(const char *s) {
		while (*s != '\0') pc(*s), s ++;
		return;
	}
	void Puts(const char *s) {
		Write(s), pc('\n'); return;
	}
	template<typename T, typename ...Args>
	void Write(T x, Args ...args) { Write(x), Write(args...); return; }
}
#define Read FastIO::Read
#define Write FastIO::Write
#define Puts FastIO::Puts
#define getchar FastIO::gc
#define putchar FastIO::pc

template<int P>
struct Static_Modint {
	int x; constexpr static int Mod = MOD;
	constexpr Static_Modint(): x(0) { }
	constexpr Static_Modint(ll _x): x(norm(_x % GetMod())) { }
	constexpr static int GetMod() { return P ? P : Mod; }
	explicit constexpr operator int() const { return x; }
	constexpr explicit operator bool() const { return x; }
	constexpr Static_Modint inv() const { return (*this).Pow(GetMod() - 2); }
	constexpr int norm(int x) const { if (x < 0) x += GetMod(); if (x >= GetMod()) x -= GetMod(); return x; }
	friend constexpr Static_Modint operator - (Static_Modint x) { x.x = x.norm(GetMod() - x.x); return x; }
	constexpr Static_Modint &operator += (const Static_Modint &oth) { x = norm(x + oth.x); return *this; }
	constexpr Static_Modint &operator -= (const Static_Modint &oth) { x = norm(x - oth.x); return *this; }
	constexpr Static_Modint &operator *= (const Static_Modint &oth) { x = 1ll * x * oth.x % GetMod(); return *this; }
	constexpr Static_Modint &operator /= (const Static_Modint &oth) { x = 1ll * x * oth.inv().x % GetMod(); return *this; }
	constexpr Static_Modint &operator ++ () { return (*this) += 1; }
	constexpr Static_Modint &operator -- () { return (*this) -= 1; }
	constexpr Static_Modint operator ++ (int) { Static_Modint tmp = (*this); return ++ (*this), tmp; }
	constexpr Static_Modint operator -- (int) { Static_Modint tmp = (*this); return -- (*this), tmp; }
	friend constexpr Static_Modint operator + (Static_Modint x, const Static_Modint &y) { return x += y; }
	friend constexpr Static_Modint operator - (Static_Modint x, const Static_Modint &y) { return x -= y; }
	friend constexpr Static_Modint operator * (Static_Modint x, const Static_Modint &y) { return x *= y; }
	friend constexpr Static_Modint operator / (Static_Modint x, const Static_Modint &y) { return x /= y; }
	constexpr Static_Modint Pow(ll y) const { Static_Modint x = *this, ans = 1; for (; y; y >>= 1, x *= x) if (y & 1) ans *= x; return ans; }
	friend constexpr Static_Modint operator + (Static_Modint x, const int &y) { return x += Static_Modint(y); }
	friend constexpr Static_Modint operator - (Static_Modint x, const int &y) { return x -= Static_Modint(y); }
	friend constexpr Static_Modint operator * (Static_Modint x, const int &y) { return x *= Static_Modint(y); }
	friend constexpr Static_Modint operator / (Static_Modint x, const int &y) { return x /= Static_Modint(y); }
	friend constexpr Static_Modint operator + (int x, const Static_Modint &y) { return Static_Modint(x) += y; }
	friend constexpr Static_Modint operator - (int x, const Static_Modint &y) { return Static_Modint(x) -= y; }
	friend constexpr Static_Modint operator * (int x, const Static_Modint &y) { return Static_Modint(x) *= y; }
	friend constexpr Static_Modint operator / (int x, const Static_Modint &y) { return Static_Modint(x) /= y; }
	friend constexpr ostream& operator << (ostream& os, const Static_Modint &x) { os << (int)x; return os; }
	friend constexpr bool operator == (const Static_Modint &x, const Static_Modint &y) { return (int)x == (int)y; }
	friend constexpr bool operator != (const Static_Modint &x, const Static_Modint &y) { return (int)x != (int)y; }
	friend constexpr bool operator <= (const Static_Modint &x, const Static_Modint &y) { return (int)x <= (int)y; }
	friend constexpr bool operator >= (const Static_Modint &x, const Static_Modint &y) { return (int)x >= (int)y; }
	friend constexpr bool operator < (const Static_Modint &x, const Static_Modint &y) { return (int)x < (int)y; }
	friend constexpr bool operator > (const Static_Modint &x, const Static_Modint &y) { return (int)x > (int)y; }
}; using mint = Static_Modint<0>;

constexpr int N = 15, M = (1 << N) + 32;
int n, m, G[N], cnt[M];
mint f[M], g[M], pw[N * N];

constexpr int lowbit(int x) {
	return x & - x;
}

void slv() {
	Read(n, m), pw[0] = 1;
	for (int i = 1; i <= m; i ++)
		pw[i] = pw[i - 1] + pw[i - 1];
	while (m --) {
		int u, v; Read(u, v);
		-- u, -- v, G[v] |= 1 << u;
	}
	int all = (1 << n) - 1;
	f[0] = 1, g[0] = 1;
	for (int S = 1; S <= all; S ++) {
		for (int u = 0; u < n; u ++)
			cnt[1 << u] = __builtin_popcount(G[u] & S);
		for (int T = S; T; T = (T - 1) & S)
			cnt[S ^ T] = cnt[lowbit(S ^ T)] + cnt[S ^ T ^ lowbit(S ^ T)];
		cnt[S] = cnt[lowbit(S)] + cnt[S ^ lowbit(S)];
		for (int _S = S ^ lowbit(S), T = _S; T; T = (T - 1) & _S)
			g[S] -= f[S ^ T] * g[T];
		f[S] = pw[cnt[S]];
		for (int T = S; T; T = (T - 1) & S)
			f[S] += g[T] * pw[cnt[S ^ T]];
		g[S] -= f[S];
	}
	Write((int)f[all], '\n');
	return;
}
void clr() {

	return;
}
bool Med;
}

int main() {
#ifdef LOCAL
	freopen("!in.in", "r", stdin);
	freopen("!out.out", "w", stdout);
	fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
	int T = 1;
//	int T = Read<int>();
	while (T --) slv(), clr();
#ifdef LOCAL
	fprintf(stderr, "%d ms\n", (int)clock());
#endif
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

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

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: 3616kb

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: 0ms
memory: 3604kb

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: 0ms
memory: 3572kb

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: 0ms
memory: 3576kb

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: 1ms
memory: 3556kb

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: 1ms
memory: 3616kb

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: 95ms
memory: 5892kb

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: 100ms
memory: 3948kb

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: 98ms
memory: 3908kb

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 繁體中文 简体中文

Server Time: 2025-01-20 05:52:38 | OpenSource Project