QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300752#7858. Basic Equation SolvingwillowAC ✓219ms3896kbC++147.3kb2024-01-08 18:54:572024-01-08 18:54:58

Judging History

你现在查看的是测评时间为 2024-01-08 18:54:58 的历史记录

  • [2024-03-20 11:12:36]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:240ms
  • 内存:4240kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2024-01-08 18:54:58]
  • 评测
  • 测评结果:100
  • 用时:219ms
  • 内存:3896kb
  • [2024-01-08 18:54:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Add(int x, int y) {
	return (x += y) >= mod ? x - mod : x;
}
int Sub(int x, int y) {
	return (x -= y) < 0 ? x + mod : x;
}
int Mul(int x, int y) {
	return 1ll * x * y % mod;
}
string eq[15][2], e;
int n, tot;
struct Dsu {
	int fa[26], can[26];
	void Init() {
		for(int i = 0; i < 26; ++ i)
			fa[i] = i, can[i] = (1 << 10) - 1;
	}
	int Get(int x) {
		return x == fa[x] ? x : fa[x] = Get(fa[x]);
	}
	int Set(int id, int l, int r) {
		int p = Get(id), to = 0;
		for(int i = l; i <= r; ++ i)
			to |= 1 << i;
		can[p] &= to;
		return can[p];
	}
	int Merge(int u, int v) {
		int x = Get(u), y = Get(v);
		if(x == y)
			return 1;
		fa[y] = x;
		can[x] &= can[y];
		return can[x];
	}
}d;
int ans, clk, to[26][26], deg[26], out[26], ways[26][10], vis[26], id[26];
vector<int> G[26];
queue<int>q;
int ffa[26], compid[26];
int Gget(int x) {
	return x == ffa[x] ? x : ffa[x] = Gget(ffa[x]);
}
void Outmerge(int x, int y) {
	ffa[Gget(y)] = Gget(x);
}
vector<int> idx[26];
int lesser[26], toid[26], canid[26];
int dp[(1 << 12) + 5][10];
int state_less[(1 << 12) + 5];
int canplace[(1 << 12) + 5];
void Calc(Dsu &now, vector<vector<int> > &less) {
// cerr << "One Calc: ";
// for(int i = 0; i < 26; ++ i) {
// 	cerr << char(now.Get(i) + 'A') << " ";
// }
// cerr << endl;
// for(int i = 0; i < 26; ++ i) {
// 	if(now.Get(i) == i) {
// 		cerr << "letter " << char(i + 'A') << ": ";
// 		for(int j = 0; j < 10; ++ j)
// 			cerr << (now.can[i] >> j & 1);
// 		cerr << endl;
// 	}
// }
	for(int i = 0; i < 26; ++ i)
		ffa[i] = i;
	++ clk;
	for(int i = 0; i < 26; ++ i) {
		deg[i] = out[i] = 0;
		G[i].clear();
	}
// for(int i = 0; i < 26; ++ i)
// 	if(i != now.Get(i))
// 		cerr << "Constraint: " << char(i + 'A') << " = " << char(now.Get(i) + 'A') << endl;
	for(int i = 0; i < 26; ++ i) {
		for(auto v : less[i]) {
			int x = now.Get(i), y = now.Get(v);
			if(x == y)
				return;
			if(to[x][y] != clk) {
				to[x][y] = clk;
// cerr << "Constraint: " << char(x + 'A') << " < " << char(y + 'A') << endl;
				G[x].push_back(y);
				Outmerge(x, y);
				++ deg[y];
				out[x] = 1;
			}
		}
	}
	int nowid = 0;
	for(int i = 0; i < 26; ++ i) {
		if(now.Get(i) != i) {
			continue;
		}
		if(Gget(i) == i) {
			idx[nowid].clear();
			compid[i] = nowid ++;
		}
	}
	for(int i = 0; i < 26; ++ i) {
		if(now.Get(i) != i) {
			continue;
		}
// cerr << i << " fa = " << Gget(i) << " ";
		idx[compid[Gget(i)]].push_back(i);
	}
// cerr << endl;
	int mul = 1;
	for(int i = 0; i < nowid; ++ i) {
		int totid = 0;
		for(auto x : idx[i]) {
			lesser[totid] = 0;
			canid[totid] = now.can[x];
			toid[x] = totid ++;
// cerr << x << ": ";
// for(auto v : G[x])
// 	cerr << v << " ";
// cerr << endl;
		}
// cerr << endl;
		for(auto x : idx[i])
			if(!deg[x])
				q.push(x);
		int sz = 0;
		while(!q.empty()) {
			int u = q.front();
			++ sz;
			q.pop();
// cerr << "? " << u << endl;
			for(auto v : G[u]) {
				lesser[toid[v]] |= lesser[toid[u]] | (1 << toid[u]);
// cerr << u << " -> " << v << endl;
				if(!(-- deg[v])) {
					q.push(v);
				}
			}
		}
// cerr << sz << endl;
		if(sz != (int)idx[i].size())
			return;
		for(int j = 0; j < 1 << sz; ++ j) {
			state_less[j] = 0;
			canplace[j] = (1 << 10) - 1;
			for(int k = 0; k < sz; ++ k) {
				if(j >> k & 1) {
					state_less[j] |= lesser[k];
					canplace[j] &= canid[k];
				}
			}
			for(int k = 0; k < 10; ++ k) {
				dp[j][k] = 0;
			}
		}
		for(int j = 0; j < 1 << sz; ++ j) {
			// cerr << j << " " << (state_less[j] & j) << " " << (canplace[j] & 1) << endl;
			if(state_less[j] == 0 && (canplace[j] & 1))
				dp[j][0] = 1; // , cerr << "! " << j << endl;
		}
		for(int j = 1; j < 10; ++ j) {
			for(int k = 0; k < 1 << sz; ++ k) {
				if(dp[k][j - 1]) {
					int tmp = (1 << sz) - 1 - k;
					for(int st = tmp; ; st = (st - 1) & tmp) {
						if(!(canplace[st] >> j & 1))
							continue;
						if((state_less[st] & st) == 0 && (state_less[st] & k) == state_less[st]) {
// if(idx[i][0] == 0 && idx[i][1] == 2 && idx[i][2] == 5)
// cerr << k << " " << j - 1 << " " << st << " " << endl;
							dp[st | k][j] = Add(dp[st | k][j], dp[k][j - 1]);
						}
						if(!st)
							break;
					}
				}
			}
		}
		mul = Mul(mul, dp[(1 << sz) - 1][9]);
// for(auto x : idx[i])
// 	cerr << x << " ";
// cerr << endl;
// cerr << "Comp: " << dp[(1 << sz) - 1][9] << endl;
	}
// cerr << "Total = " << mul << endl;
	ans = Add(ans, mul);
}
void Solve(int pos, Dsu now, vector<vector<int> > less) {
	if(pos == tot) {
		Calc(now, less);
		return;
	}
	int len = eq[pos][0].length();
	for(int i = 0; i < len; ++ i) {
		Dsu nxt = now;
		if(isdigit(eq[pos][0][i]) && isdigit(eq[pos][1][i])) {
			int l = eq[pos][0][i] - '0', r = eq[pos][1][i] - '0';
			if(l > r)
				break;
			if(l < r)
				Solve(pos + 1, nxt, less);
			if(eq[pos][0][i] != eq[pos][1][i]) {
				break;
			}
		}
		if(isdigit(eq[pos][0][i])) {
			int l = eq[pos][0][i] - '0', r = eq[pos][1][i] - 'A';
			if(nxt.Set(r, l + 1, 9))
				Solve(pos + 1, nxt, less);
			if(!now.Set(r, l, l))
				break;
			continue;
		}
		if(isdigit(eq[pos][1][i])) {
			int l = eq[pos][0][i] - 'A', r = eq[pos][1][i] - '0';
			if(nxt.Set(l, 0, r - 1))
				Solve(pos + 1, nxt, less);
			if(!now.Set(l, r, r))
				break;
			continue;
		}
		int l = eq[pos][0][i] - 'A', r = eq[pos][1][i] - 'A';
// cerr << eq[pos][0][i] << " < " << eq[pos][1][i] << endl;
		less[l].push_back(r);
		Solve(pos + 1, nxt, less);
		less[l].pop_back();
		if(!now.Merge(l, r))
			break;
	}
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	d.Init();
	for(int i = 1; i <= n; ++ i) {
		cin >> e;
		string lef = "", rig = "";
		int len = e.length(), pos = -1;
		for(int j = 0; j < len; ++ j) {
			if(e[j] == '=' || e[j] == '>' || e[j] == '<') {
				pos = j;
				break;
			}
		}
		for(int j = 0; j < pos; ++ j)
			lef += e[j];
		for(int j = pos + 1; j < len; ++ j)
			rig += e[j];
		if(e[pos] == '=') {
			while(lef.length() < rig.length())
				lef = '0' + lef;
			while(rig.length() < lef.length())
				rig = '0' + rig;
			int l = lef.length();
			for(int j = 0; j < l; ++ j) {
				if(isdigit(lef[j]) && isdigit(rig[j])) {
					if(lef[j] != rig[j]) {
						return 0 * puts("0");
					}
					continue;
				}
				if(isdigit(lef[j])) {
					d.Set(rig[j] - 'A', lef[j] - '0', lef[j] - '0');
					continue;
				}
				if(isdigit(rig[j])) {
					d.Set(lef[j] - 'A', rig[j] - '0', rig[j] - '0');
					continue;
				}
				d.Merge(lef[j] - 'A', rig[j] - 'A');
			}
			continue;
		}
		if(e[pos] == '>') {
			swap(lef, rig);
		}
		if(rig.length() < lef.length()) {
			int diff = lef.length() - rig.length();
			for(int j = 0; j < diff; ++ j) {
				if(!d.Set(lef[j] - 'A', 0, 0)) {
					return 0 * puts("0");
				}
			}
			string tmp = "";
			for(int j = diff; j < (int)lef.length(); ++ j) {
				tmp += lef[j];
			}
			lef = tmp;
			assert(lef.length() == rig.length());
		}
		else {
			while(lef.length() < rig.length()) {
				lef = '0' + lef;
			}
		}
		eq[tot][0] = lef;
		eq[tot][1] = rig;
// cerr << eq[tot][0] << " < " << eq[tot][1] << endl;
		tot ++;
	}
	Solve(0, d, vector<vector<int> >(26, vector<int>()));
	printf("%d\n", ans);
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3728kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: 0
Accepted
time: 3ms
memory: 3792kb

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: 6ms
memory: 3800kb

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: 9ms
memory: 3796kb

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: 219ms
memory: 3784kb

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: 121ms
memory: 3896kb

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

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

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: 3ms
memory: 3760kb

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

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

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

input:

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

output:

467745652

result:

ok single line: '467745652'

Test #17:

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

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed