QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351016#7858. Basic Equation Solvingushg8877AC ✓1676ms3952kbC++143.3kb2024-03-11 12:07:052024-03-11 12:07:05

Judging History

你现在查看的是测评时间为 2024-03-11 12:07:05 的历史记录

  • [2024-03-20 11:12:45]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1667ms
  • 内存:3916kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2024-03-11 12:07:05]
  • 评测
  • 测评结果:100
  • 用时:1676ms
  • 内存:3952kb
  • [2024-03-11 12:07:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MOD=998244353;
int n,d[10];string a[10],b[10];char op[10];
int fa[26],dsu[26],id[26],ord[26],lk[1<<11|10],le[26],ri[26],Le[1<<11|15],Ri[1<<11|15];
int f[11][1<<11|15];
vector<int> edg[26];// 连边方向:小->大
int ans=0;
inline int find(int *fa,int x){
	while(x^fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
bool number(char c){return '0'<=c&&c<='9';}
bool letter(char c){return 'A'<=c&&c<='Z';}
void chkmin(int &x,int y){if(x>y)x=y;}
void chkmax(int &x,int y){if(x<y)x=y;}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
void solve(){
	for(int i=0;i<26;i++) fa[i]=dsu[i]=i,edg[i].clear();
	for(int i=0;i<26;i++) le[i]=0,ri[i]=9;
	for(int i=0;i<n;i++) for(int j=0;j<=d[i];j++) {
		if(letter(a[i][j])&&letter(b[i][j])) fa[find(fa,a[i][j]-'A')]=find(fa,b[i][j]-'A');
		if(op[i]=='='||j<d[i]){
			if(number(a[i][j])&&number(b[i][j])&&a[i][j]!=b[i][j]) return;
			if(number(a[i][j])&&letter(b[i][j])){
				chkmax(le[b[i][j]-'A'],a[i][j]-'0');
				chkmin(ri[b[i][j]-'A'],a[i][j]-'0');
			}if(number(b[i][j])&&letter(a[i][j])){
				chkmax(le[a[i][j]-'A'],b[i][j]-'0');
				chkmin(ri[a[i][j]-'A'],b[i][j]-'0');
			}if(letter(a[i][j])&&letter(b[i][j])) dsu[find(dsu,a[i][j]-'A')]=dsu[find(dsu,b[i][j]-'A')];
		}else{
			if(number(a[i][j])&&number(b[i][j])&&a[i][j]>b[i][j]) return;
			if(number(a[i][j])&&letter(b[i][j])) chkmax(le[b[i][j]-'A'],a[i][j]-'0'+1);
			if(number(b[i][j])&&letter(a[i][j])) chkmin(ri[a[i][j]-'A'],b[i][j]-'0'-1);
			if(letter(a[i][j])&&letter(b[i][j])) edg[b[i][j]-'A'].push_back(a[i][j]-'A');
		}
	}
	int prd=1;
	for(int i=0;i<26;i++) if(fa[i]==i){
		vector<int> vec;
		for(int j=0;j<26;j++) if(find(fa,j)==i) vec.push_back(j);
		int n=0;
		for(int j:vec){
			if(dsu[j]==j) ord[n]=j,id[j]=n++;
			else{
				chkmax(le[find(dsu,j)],le[j]);
				chkmin(ri[find(dsu,j)],ri[j]);
			}
		}
		for(int j=0;j<n;j++) if(ri[j]<le[j]) return;
		for(int j:vec) id[j]=id[find(dsu,j)];
		for(int i=0;i<n;i++) Le[1<<i]=le[ord[i]],Ri[1<<i]=ri[ord[i]];
		for(int i=0;i<(1<<n);i++) lk[i]=0;
		for(int j:vec) for(int k:edg[j]) 
			if(id[j]==id[k]) return; else lk[1<<id[j]]|=1<<id[k];
		for(int S=1;S<(1<<n);S++) if((S&-S)!=S){
			lk[S]=lk[S^(S&-S)]|lk[S&-S];
			Le[S]=max(Le[S^(S&-S)],Le[S&-S]);
			Ri[S]=min(Ri[S^(S&-S)],Ri[S&-S]);
		}
		for(int i=0;i<=10;i++) for(int S=0;S<(1<<n);S++) f[i][S]=0;
		f[0][0]=1;
		for(int i=1;i<=10;i++) for(int S=0;S<(1<<n);S++) {
			f[i][S]=f[i-1][S];
			for(int T=S;T;T=(T-1)&S) if(!(lk[S]&T)&&Le[T]<=i-1&&i-1<=Ri[T]) 
				add(f[i][S],f[i-1][S^T]);
		}
		prd=1ll*prd*f[10][(1<<n)-1]%MOD;
	}
	add(ans,prd);
	return;
}
void dfs(int p){
	if(p==n){
		solve();return;
	}
	if(op[p]=='=') d[p]=a[p].size()-1,dfs(p+1);
	else{
		for(int i=0;i<a[p].size();i++){
			d[p]=i;
			dfs(p+1);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++){
		string p,s,t;
		cin>>p;
		for(int j=0;j<p.size();j++){
			if(p[j]!='<'&&p[j]!='='&&p[j]!='>') t+=p[j];
			else op[i]=p[j],swap(s,t);
		}
		if(op[i]=='>') swap(s,t),op[i]='<';
		while(a[i].size()+s.size()<t.size()) a[i]+='0';
		while(b[i].size()+t.size()<s.size()) b[i]+='0';
		a[i]+=s,b[i]+=t;
	}
	dfs(0);
	cout<<ans<<'\n';
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

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

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: 48ms
memory: 3704kb

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: 122ms
memory: 3656kb

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: 1654ms
memory: 3664kb

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: 1676ms
memory: 3952kb

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

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

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

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

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

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

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

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed