QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269147#7858. Basic Equation Solvingucup-team1209#AC ✓113ms4100kbC++204.5kb2023-11-29 13:24:542024-10-14 18:02:47

Judging History

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

  • [2024-10-14 18:02:47]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:113ms
  • 内存:4100kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2023-11-29 13:24:55]
  • 评测
  • 测评结果:100
  • 用时:82ms
  • 内存:3772kb
  • [2023-11-29 13:24:54]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin, std::cout;
using ll = long long;
int n;

const int N = 26;
const int mod = 998244353;
using u64 = unsigned long long;
std::string l[N], r[N];
int op[N];
int m;

const int M = 11;

int edge[1 << M];
int dp[1 << M];
int mask[1 << M];
int min[M], max[M];
void inc(int & x, int y) {
	if((x += y) >= mod) {
		x -= mod;
	}
}
int solve(int n) {
	memset(mask, 0, 4 << n);
	memset(dp, 0, 4 << n);
	for(int i = 0;i < 1 << n;++i) {
		for(int j = 0;j < n;++j) if((i >> j & 1) == 0) {
			if((edge[j] & i) == edge[j]) {
				mask[i] |= 1 << j;
			}
		}
	}
	dp[0] = 1;
	for(int i = 0;i <= 9;++i) {
		int valid = 0;
		for(int j = 0;j < n;++j) if(min[j] <= i && i <= max[j]) {
			valid |= 1 << j;
		}
		for(int j = (1 << n) - 1;j >= 0;--j) if(int v = dp[j]) {
			int add = valid & mask[j];
			for(int k = add;k;k = (k - 1) & add) {
				inc(dp[j | k], v);
			}
		}
	}
	memset(edge, 0, n << 2);
	return dp[(1 << n) - 1];
}

struct graph {
	int l[N], r[N];
	int gt[N][N];
	int eq[N][N];
	int col[N];
	int colpb[N];

	int le[N], ri[N];
	int G[N][N];
	void lim(int x, int L, int R) {
		l[x] = std::max(l[x], L);
		r[x] = std::min(r[x], R);
	}
	void init() {
		for(int i = 0;i < N;++i) {
			l[i] = 0, r[i] = 9;
			le[i] = 0, ri[i] = 9;
			col[i] = -1;
			colpb[i] = -1;
		}
	}
	int solve() {
		static std::queue<int> Q;
		int cc = 0;
		for(int i = 0;i < N;++i) if(col[i] == -1) {
			col[i] = cc; Q.push(i);
			for(;Q.size();) {
				int x = Q.front(); Q.pop();
				for(int j = 0;j < N;++j) if(eq[x][j] && col[j] == -1) {
					col[j] = cc; Q.push(j);
				}
			}
			++cc;
		}
		for(int i = 0;i < N;++i) {
			le[col[i]] = std::max(le[col[i]], l[i]);
			ri[col[i]] = std::min(ri[col[i]], r[i]);
			for(int j = 0;j < N;++j) if(gt[i][j]) {
				G[col[i]][col[j]] = 1;
			}
		}
		for(int i = 0;i < cc;++i) col[i] = -1;
		int res = 1;

		for(int i = 0;i < cc;++i) if(col[i] == -1) {
			static std::vector<int> con; 
			col[i] = 0; Q.push(i); con = {i};
			for(;Q.size();) {
				int x = Q.front(); Q.pop();
				for(int j = 0;j < cc;++j) if((G[x][j] || G[j][x]) && col[j] == -1) {
					col[j] = 0; Q.push(j);
					con.push_back(j);
				}
			}
			int m = con.size();
			for(int i = 0;i < m;++i) {
				min[i] = le[con[i]];
				max[i] = ri[con[i]];
				for(int j = 0;j < m;++j) {
					edge[i] |= G[con[i]][con[j]] << j;
				}
			}
			res = (u64) res * ::solve(m) % mod;
		}

		return res;
	}
} G;

int ans;
void dfs0(int x, graph t) {
	if(x == m) {
		inc(ans, t.solve());
		return ;
	}
	for(int lcp = 0;lcp < (int) l[x].size();++lcp) {
		graph z = t;
		int bad = 0;
		for(int j = 0;j < lcp;++j) {
			int a = isalpha(l[x][j]);
			int b = isalpha(r[x][j]);
			if(a && b) {
				z.eq[l[x][j] - 'A'][r[x][j] - 'A'] = 1;
				z.eq[r[x][j] - 'A'][l[x][j] - 'A'] = 1;
			}
			if(!a && !b) {
				if(l[x][j] != r[x][j]) {
					bad = 1;
					break;
				}
			}
			char A = l[x][j], B = r[x][j];
			if(a && !b) z.lim(A - 'A', B - '0', B - '0');
			if(!a && b) z.lim(B - 'A', A - '0', A - '0');
		}
		if(bad) continue;
		int a = isalpha(l[x][lcp]);
		int b = isalpha(r[x][lcp]);
		if(!a && !b) {
			if(l[x][lcp] <= r[x][lcp]) {
				continue;
			}
		} else if(a && b) {
			z.gt[l[x][lcp] - 'A'][r[x][lcp] - 'A'] = 1;
		} else if(a && !b) {
			z.lim(l[x][lcp] - 'A', r[x][lcp] - '0' + 1, 9);
		} else if(!a && b) {
			z.lim(r[x][lcp] - 'A', 0, l[x][lcp] - '0' - 1);
		}
		dfs0(x + 1, z);
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	G.init();
	for(int i = 0;i < n;++i) {
		std::string s, l, r;
		char op;
		cin >> s;
		for(int i = 0;i < (int) s.size();++i) {
			if(s[i] == '=' || s[i] == '<' || s[i] == '>') {
				op = s[i];
				l = std::string(s.begin(), s.begin() + i);
				r = std::string(s.begin() + i + 1, s.end());
			}
		}
		for(;l.size() < r.size();) l = "0" + l;
		for(;l.size() > r.size();) r = "0" + r;
		if(op == '=') {
			for(int j = 0;j < (int) l.size();++j) {
				int a = isalpha(l[j]);
				int b = isalpha(r[j]);
				if(a && b) {
					G.eq[l[j] - 'A'][r[j] - 'A'] = 1;
					G.eq[r[j] - 'A'][l[j] - 'A'] = 1;
				}
				if(!a && !b) {
					if(l[j] != r[j]) {
						puts("0");
						return 0;
					}
				}
				if(b) std::swap(l[j], r[j]), std::swap(a, b);
				if(a && !b) {
					G.lim(l[j] - 'A', r[j] - '0', r[j] - '0');
				}
			}
		} else {
			if(op == '<') op = '>', std::swap(l, r);
			::l[m] = l;
			::r[m] = r;
			::op[m++] = op;
		}
	}

	dfs0(0, G);

	cout << ans << '\n';
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

4
AB>CD
E<A
BC>FF
EF>F1

output:

23645065

result:

ok single line: '23645065'

Test #4:

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: 0
Accepted
time: 9ms
memory: 3908kb

input:

10
KG<EI
EJ>DA
EB<IH
EB>JG
KF<CF
JC>FC
IC<BJ
FI>HH
KD>AH
AE>GJ

output:

87744507

result:

ok single line: '87744507'

Test #7:

score: 0
Accepted
time: 13ms
memory: 4100kb

input:

10
EK<GM
EL<DC
DH>IH
EF>BL
IM<LL
EH<JA
DJ<AL
GL>MB
DB>FM
AI<HA

output:

665533468

result:

ok single line: '665533468'

Test #8:

score: 0
Accepted
time: 21ms
memory: 3908kb

input:

10
OD<FK
FJ>NL
NH>KB
KM>CA
CI>JH
CI<AH
CE>GI
CO<EG
FA>HA
FA<IJ

output:

878923575

result:

ok single line: '878923575'

Test #9:

score: 0
Accepted
time: 113ms
memory: 3904kb

input:

10
YH>UQ
UQ>FD
YZ>MK
FY<GO
YV<QW
UV<VJ
UZ>EB
EQ>LX
VP>ZF
LZ>TS

output:

867624189

result:

ok single line: '867624189'

Test #10:

score: 0
Accepted
time: 111ms
memory: 4068kb

input:

10
YH<UL
UD<FY
FK<MU
MM<GO
GG<QW
QJ<VQ
VZ<EB
EG<LX
LZ<ZP
ZV<TS

output:

57935948

result:

ok single line: '57935948'

Test #11:

score: 0
Accepted
time: 4ms
memory: 4056kb

input:

6
EDDC>AB5A
B<C
E9A9B>CACAA
DE2>A0D
DBCDAC>AED3D5
AAA>BB5

output:

169889581

result:

ok single line: '169889581'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

9
C<B
A>B
FDF2<FBDB
DB>B4
CF>DA
EF4<D1A
B8<A5
B3>BF
FFA<D5B

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3816kb

input:

5
SP6<GCT
J0RFZ<ZZLUX
UDY7<UEVX
C1CQ>FXTG
SOCT07<MEABU8

output:

603602671

result:

ok single line: '603602671'

Test #14:

score: 0
Accepted
time: 4ms
memory: 4004kb

input:

7
F>M
G8F<KC5
F06<E8G
H5J<BJE
M8CDE<DIGMC
AE08>EFI7
DM>CI

output:

821791712

result:

ok single line: '821791712'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

10
PS1>O9O
G76>F8S
J<S
SB>Y4
WS<VM
E<N
ZR<CV
G8T>XPJ
J<A
KT<LS

output:

97272892

result:

ok single line: '97272892'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

4
K1TVV0>TOB4QTH
E5U5C9>QGDEGU
Q9LW3SK>LWFRP
DXUQM=V4N4

output:

467745652

result:

ok single line: '467745652'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

5
BC5F<AC3F
FA4<D48306EDD
EFDD>FDABE
CF5C<AFDDB
FAF<C387

output:

808992671

result:

ok single line: '808992671'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

input:

9
N=A8
TT<QO3G
LS>JV
TSG>U5F
D<A934
FK<HKG
O>S1
GT<BBCX
SG>S

output:

929594610

result:

ok single line: '929594610'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed