QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290422 | #7. 主旋律 | MoRanSky | 100 ✓ | 733ms | 4296kb | C++20 | 1.7kb | 2023-12-24 23:36:21 | 2023-12-24 23:36:23 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N = 15, P = 1e9 + 7;
int n, m, g[N], c[1 << N], f[1 << N], pw2[N * N + 5], h[1 << N], w[1 << N];
void inline del(int &x, int y) {
x -= y;
if (x < 0) x += P;
}
void inline add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
// a in x to b in y
int inline G(int x, int y) {
int o = 0;
for (int i = 0; i < n; i++)
if (x >> i & 1) o += c[g[i] & y];
return o;
}
void inline upd(int i) {
int re = ((1 << n) - 1) ^ i;
for (int A = re; ; A = (A - 1) & re) {
del(h[A | i], 1ll * h[A] * f[i] % P);
if (!A) break;
}
}
int main() {
read(n), read(m);
while (m--) {
int a, b; read(a), read(b);
--a, --b;
g[a] |= 1 << b;
}
pw2[0] = 1;
for (int i = 1; i <= n * n; i++) pw2[i] = pw2[i - 1] * 2 % P;
for (int i = 1; i < (1 << n); i++) c[i] = c[i - (i & -i)] + 1;
for (int i = 0; i < (1 << n); i++) w[i] = G(i, i);
h[0] = 1;
for (int i = 1; i < (1 << n); i++) {
f[i] = pw2[w[i]];
for (int j = i; j; j = (j - 1) & i) {
int v = w[i ^ j] + G(j, i ^ j);
add(f[i], 1ll * h[j] * pw2[v] % P);
}
upd(i);
}
printf("%d\n", f[(1 << n) - 1]);
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 3648kb
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: 3580kb
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: 3772kb
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: 3516kb
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: 3768kb
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: 3596kb
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: 3ms
memory: 3644kb
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: 727ms
memory: 4004kb
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: 730ms
memory: 4140kb
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: 733ms
memory: 4296kb
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'