QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#470653 | #7858. Basic Equation Solving | ucup-team052# | WA | 0ms | 4036kb | C++14 | 8.8kb | 2024-07-10 15:42:29 | 2024-07-10 15:42:30 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
template <typename _T>
inline void read(_T &f) {
f = 0; _T fu = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
f *= fu;
}
template <typename T>
void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x + 48);
else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
print(x); putchar(t);
}
const int md = 998244353;
inline int add(int x, int y) {
if (x + y >= md) return x + y - md;
return x + y;
}
inline void addx(int &x, int y) {
x += y;
if (x >= md) x -= md;
}
inline int sub(int x, int y) {
if (x < y) return x - y + md;
return x - y;
}
inline void subx(int &x, int y) {
x -= y;
if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1; x = mul(x, x);
}
return ans;
}
const int N = 11;
int a[N][55], b[N][55], op[N], len[N];
char c[55];
int n, ans;
int dp[1 << N], ndp[1 << N], ok[1 << N], f[26], id[26], L[26], R[26], big[26], vis[26], seq[26];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
int g[26][26][26], e[26][26], l[26][26], r[26][26];
void dfs(int u) {
auto cpy = [&]() {
memcpy(l[u], l[u - 1], sizeof(l[u]));
memcpy(r[u], r[u - 1], sizeof(r[u]));
memcpy(g[u], g[u - 1], sizeof(g[u]));
};
if (u > n) {
cpy();
for (int i = 0; i <= 25; i++) f[i] = i;
for (int i = 0; i <= 25; i++) {
for (int j = i + 1; j <= 25; j++) {
if (g[u][i][j] == 3) {
int x = find(i), y = find(j);
f[x] = f[y] = min(x, y);
}
}
}
int m = 0;
for (int i = 0; i < 26; i++) {
if (find(i) == i) {
id[i] = m;
++m;
}
}
memset(e, 0, sizeof(e));
for (int i = 0; i < m; i++) L[i] = 1, R[i] = 10;
int flag = 1;
for (int i = 0; i <= 25; i++) {
for (int j = 0; j <= 25; j++) {
int x = id[find(i)], y = id[find(j)];
L[x] = max(L[x], l[u][i]);
R[x] = min(R[x], r[u][i]);
if (g[u][i][j] == 1) {
if (x == y) flag = 0;
if (e[x][y] && e[x][y] != 1) flag = 0;
e[x][y] = 1;
}
if (g[u][i][j] == 2) {
if (x == y) flag = 0;
if (e[x][y] && e[x][y] != 2) flag = 0;
e[x][y] = 2;
}
if (g[u][i][j] == 3) {
assert(x == y);
/*
if (e[x][y] && e[x][y] != 3) flag = 0;
e[x][y] = 3;
*/
}
}
}
for (int i = 0; i < m; i++) {
// fprintf(stderr, "L[%d] = %d, R[%d] = %d\n", i, L[i], i, R[i]);
if (L[i] > R[i]) {
flag = 0;
break;
}
}
if (!flag) return;
memset(vis, 0, sizeof(vis));
int res = 1;
for (int i = 0; i < m; i++) {
if (vis[i]) continue;
queue <int> q; q.push(i); vis[i] = 1;
int len = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
seq[len] = u; ++len;
for (int j = 0; j < m; j++) {
if (!vis[j] && e[u][j]) {
vis[j] = 1; q.push(j);
}
}
}
for (int j = 0; j < len; j++) {
big[j] = 0;
for (int k = 0; k < len; k++) {
if (e[seq[j]][seq[k]] == 1) {
big[j] |= (1 << k);
}
}
}
memset(dp, 0, (1 << len) * 4);
dp[0] = 1;
for (int num = 1; num <= 10; num++) {
memset(ndp, 0, (1 << len) * 4);
for (int j = 0; j < (1 << len); j++) {
ok[j] = 1;
for (int k = 0; k < len; k++) {
if ((j >> k) & 1) {
if (num < L[seq[k]] || R[seq[k]] < num) {
ok[j] = 0;
break;
}
}
}
}
for (int j = 0; j < (1 << len); j++) {
for (int s = j; ; s = (s - 1) & j) {
if (ok[s]) {
int cando = 1;
for (int k = 0; k < len; k++) {
if ((s >> k) & 1) {
if ((big[k] & (j ^ s)) != big[k]) {
cando = 0;
break;
}
}
}
if (cando) ndp[j] = add(ndp[j], dp[j ^ s]);
}
if (!s) break;
}
}
memcpy(dp, ndp, (1 << len) * 4);
}
res = mul(res, dp[(1 << len) - 1]);
}
ans = add(ans, res);
return;
}
auto addeq = [&](int x, int y) {
if (x < 0 && y < 0) return x == y;
if (x < 0 && y >= 0) swap(x, y);
if (x >= 0 && y < 0) {
l[u][x] = max(l[u][x], -y), r[u][x] = min(r[u][x], -y);
return l[u][x] <= r[u][x];
}
if (g[u][x][y] && g[u][x][y] != 3) {
return false;
}
g[u][x][y] = g[u][y][x] = 3;
return true;
};
auto add1 = [&](int x, int y) {
if (x < 0 && y < 0) return -x > -y;
if (x < 0 && y >= 0) {
r[u][y] = min(r[u][y], -x - 1);
return l[u][y] <= r[u][y];
}
if (x >= 0 && y < 0) {
l[u][x] = max(l[u][x], -y + 1);
return l[u][x] <= r[u][x];
}
if (g[u][x][y] && g[u][x][y] != 1) {
return false;
}
g[u][x][y] = 1; g[u][y][x] = 2;
return true;
};
if (op[u] == 1) {
for (int i = 1; i <= len[u]; i++) {
cpy();
int flag = 1;
for (int j = i + 1; j <= len[u]; j++) {
if (!addeq(a[u][j], b[u][j])) {
flag = 0;
break;
}
}
if (!add1(a[u][i], b[u][i])) flag = 0;
if (flag) dfs(u + 1);
}
}
if (op[u] == 3) {
cpy();
for (int i = 1; i <= len[u]; i++) {
if (!addeq(a[u][i], b[u][i])) {
return;
}
}
dfs(u + 1);
}
}
int main() {
read(n);
for (int i = 0; i <= 25; i++) l[0][i] = 1, r[0][i] = 10;
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
int len = strlen(c + 1), lena = 0, lenb = 0;
for (int j = 1; j <= len; j++) {
if ((c[j] >= 'A' && c[j] <= 'Z') || (c[j] >= '0' && c[j] <= '9')) {
if (!op[i]) {
++lena;
if (c[j] >= 'A' && c[j] <= 'Z') a[i][lena] = c[j] - 'A';
else a[i][lena] = -(c[j] - '0') - 1;
} else {
++lenb;
if (c[j] >= 'A' && c[j] <= 'Z') b[i][lenb] = c[j] - 'A';
else b[i][lenb] = -(c[j] - '0') - 1;
}
} else {
if (c[j] == '>') op[i] = 1;
if (c[j] == '<') op[i] = 2;
if (c[j] == '=') op[i] = 3;
}
}
reverse(a[i] + 1, a[i] + lena + 1);
reverse(b[i] + 1, b[i] + lenb + 1);
while (lena < lenb) {
++lena;
a[i][lena] = -1;
}
while (lenb < lena) {
++lenb;
b[i][lenb] = -1;
}
::len[i] = lena;
if (op[i] == 2) {
op[i] = 1;
for (int j = 1; j <= lena; j++) swap(a[i][j], b[i][j]);
}
}
dfs(1);
ans = mul(ans, fpow(fpow(10, md - 2), 22));
print(ans, '\n');
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4036kb
input:
1 P=NP
output:
1000
result:
wrong answer 1st lines differ - expected: '766136394', found: '1000'