QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289606#7858. Basic Equation Solvingucup-team191#AC ✓82ms3916kbC++236.2kb2023-12-23 19:42:432023-12-23 19:42:44

Judging History

你现在查看的是测评时间为 2023-12-23 19:42:44 的历史记录

  • [2024-10-14 18:02:56]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:89ms
  • 内存:3876kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2023-12-23 19:42:44]
  • 评测
  • 测评结果:100
  • 用时:82ms
  • 内存:3916kb
  • [2023-12-23 19:42:43]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=310,MOD=998244353,C=26;
const ll LLINF=1ll<<60;
const char en='\n';

int n,an,par[N],lo[N],hi[N];
bool bio[N];
char ti[N];
string a[N],b[N];
vector<pii> undir,dir;
vi ch[N],rch[N],locha[N],hicha[N];

int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

void ad(int&a,int b)
{
	a+=b;
	if (a>=MOD) a-=MOD;
}

int mul(int a,int b)
{
	return a*1ll*b%MOD;
}

int pot(int n,int k)
{
	if (k==0) return 1;
	int r=pot(n,k/2);
	r=mul(r,r);
	if (k%2) r=mul(r,n);
	return r;
}

int find(int i)
{
	if (i==par[i]) return i;
	return par[i]=find(par[i]);
}

void mer(int a,int b)
{
	a=find(a);
	b=find(b);
	if (a==b) return;
	par[a]=b;
}

vi cucomp;

void dfs1(int i)
{
	bio[i]=1;
	cucomp.pb(i);
	for (auto x: ch[i]) if (!bio[x]) dfs1(x);
	for (auto x: rch[i]) if (!bio[x]) dfs1(x);
}

int solveComp(vi lo,vi hi,vi edg)
{
	//edg: (edg[i]>>j)&1 if i<j
	//topological order
	int n=lo.size();
	vi dp(1<<n);
	dp[0]=1;
	for (int col=0;col<10;++col)
	{
		for (int i=n-1;i>=0;--i) if (col>=lo[i] && col<=hi[i])
		{
			int subs=(1<<n)-1-edg[i]-(1<<i);
			for (int c=subs;c;c=(c-1)&subs) ad(dp[c|(1<<i)],dp[c]);
			ad(dp[1<<i],dp[0]);
		}
	}
	return dp[(1<<n)-1];
}

vi redor;

void dfs2(int i)
{
	bio[i]=1;
	for (auto x: ch[i]) if (!bio[x]) dfs2(x);
	redor.pb(i);
}

int solve()
{
	//use undir and dir, as well as lo and hi
	for (int i=0;i<C;++i)
	{
		par[i]=i;
		ch[i].clear();
		rch[i].clear();
		bio[i]=0;
		lo[i]=0;
		hi[i]=9;
		for (auto x: locha[i]) lo[i]=max(lo[i],x);
		for (auto x: hicha[i]) hi[i]=min(hi[i],x);
		//if (i<6) cout<<i<<' '<<lo[i]<<' '<<hi[i]<<endl;
	}
	/*cout<<"undir:"<<endl;
	for (auto x: undir) cout<<x.x<<' '<<x.y<<endl;
	cout<<"dir:"<<endl;
	for (auto x: dir) cout<<x.x<<' '<<x.y<<endl;*/
	for (auto x: undir) mer(x.x,x.y);
	//look for connected components
	for (auto y: dir)
	{
		int u=find(y.x),v=find(y.y);
		if (u==v) return 0;
		ch[u].pb(v);
		rch[v].pb(u);
	}
	vi merlo(C),merhi(C,9);
	for (int i=0;i<C;++i)
	{
		merlo[find(i)]=max(merlo[find(i)],lo[i]);
		merhi[find(i)]=min(merhi[find(i)],hi[i]);
	}
	int an=1;
	for (int i=0;i<C;++i) if (par[i]==i && !bio[i])
	{
		//if (i<8) cout<<"starting comp "<<i<<endl;
		cucomp.clear();
		dfs1(i);
		redor.clear();
		for (auto x: cucomp) bio[x]=0;
		for (auto x: cucomp) if (!bio[x]) dfs2(x);
		reverse(all(redor));
		//redor is now topological order
		vi lov(redor.size()),hiv(redor.size()),edg(redor.size()),inor(C,-1);
		for (int j=0;j<(int)redor.size();++j) inor[redor[j]]=j;
		for (int j=0;j<(int)redor.size();++j)
		{
			lov[j]=merlo[redor[j]];
			hiv[j]=merhi[redor[j]];
			for (auto x: ch[redor[j]]) if (inor[x]!=-1) edg[j]|=1<<inor[x];
		}
		/*cout<<i<<endl;
		for (auto x: redor) cout<<x<<' ';
		cout<<endl;
		for (auto x: lov) cout<<x<<' ';
		cout<<endl;
		for (auto x: hiv) cout<<x<<' ';
		cout<<endl;
		for (auto x: edg) cout<<x<<' ';
		cout<<endl;*/
		int musa=solveComp(lov,hiv,edg);
		//cout<<musa<<endl<<endl;
		an=mul(an,musa);
	}
	//cout<<an<<endl;
	return an;
}

void rek(int d)
{
	if (d==n)
	{
		ad(an,solve());
		return;
	}
	if (ti[d]=='=')
	{
		while (a[d].size()<b[d].size()) a[d]="0"+a[d];
		while (b[d].size()<a[d].size()) b[d]="0"+b[d];
		int sz=a[d].size();
		for (int i=0;i<sz;++i)
		{
			if (a[d][i]>='0' && a[d][i]<='9' && b[d][i]>='0' && b[d][i]<='9' && a[d][i]!=b[d][i]) return;
		}
		for (int i=0;i<sz;++i)
		{
			if (a[d][i]>='0' && a[d][i]<='9')
			{
				if (b[d][i]>='A' && b[d][i]<='Z')
				{
					locha[b[d][i]-'A'].pb(a[d][i]-'0');
					hicha[b[d][i]-'A'].pb(a[d][i]-'0');
				}
			}
			else
			{
				if (b[d][i]>='0' && b[d][i]<='9')
				{
					locha[a[d][i]-'A'].pb(b[d][i]-'0');
					hicha[a[d][i]-'A'].pb(b[d][i]-'0');
				}
				else
				{
					undir.pb({a[d][i]-'A',b[d][i]-'A'});
				}
			}
		}
		rek(d+1);
		for (int i=0;i<sz;++i)
		{
			if (a[d][i]>='0' && a[d][i]<='9')
			{
				if (b[d][i]>='A' && b[d][i]<='Z')
				{
					locha[b[d][i]-'A'].pop_back();
					hicha[b[d][i]-'A'].pop_back();
				}
			}
			else
			{
				if (b[d][i]>='0' && b[d][i]<='9')
				{
					locha[a[d][i]-'A'].pop_back();
					hicha[a[d][i]-'A'].pop_back();
				}
				else
				{
					undir.pop_back();
				}
			}
		}
	}
	if (ti[d]=='>')
	{
		ti[d]='<';
		swap(a[d],b[d]);
	}
	if (ti[d]=='<')
	{
		string x=a[d],y=b[d];
		while (x.size()<y.size()) x="0"+x;
		while (y.size()<x.size()) y="0"+y;
		int sz=x.size();
		for (int i=0;i<sz;++i)
		{
			if (x[i]>='0' && x[i]<='9')
			{
				if (y[i]>='0' && y[i]<='9')
				{
					if (x[i]<y[i]) rek(d+1);
					if (x[i]!=y[i]) break;
				}
				else
				{
					locha[y[i]-'A'].pb(x[i]-'0'+1);
					rek(d+1);
					locha[y[i]-'A'].pop_back();
					locha[y[i]-'A'].pb(x[i]-'0');
					hicha[y[i]-'A'].pb(x[i]-'0');
				}
			}
			else
			{
				if (y[i]>='0' && y[i]<='9')
				{
					hicha[x[i]-'A'].pb(y[i]-'0'-1);
					rek(d+1);
					hicha[x[i]-'A'].pop_back();
					locha[x[i]-'A'].pb(y[i]-'0');
					hicha[x[i]-'A'].pb(y[i]-'0');
				}
				else
				{
					dir.pb({x[i]-'A',y[i]-'A'});
					rek(d+1);
					dir.pop_back();
					undir.pb({x[i]-'A',y[i]-'A'});
				}
			}
		}
		
		//undo
		
		for (int i=0;i<sz;++i)
		{
			if (x[i]>='0' && x[i]<='9')
			{
				if (y[i]>='0' && y[i]<='9')
				{
					if (x[i]!=y[i]) break;
				}
				else
				{
					locha[y[i]-'A'].pop_back();
					hicha[y[i]-'A'].pop_back();
				}
			}
			else
			{
				if (y[i]>='0' && y[i]<='9')
				{
					locha[x[i]-'A'].pop_back();
					hicha[x[i]-'A'].pop_back();
				}
				else
				{
					undir.pop_back();
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int inv10=pot(10,MOD-2);
	cin>>n;
	for (int i=0;i<n;++i)
	{
		string x;
		cin>>x;
		for (int j=0;j<(int)x.size();++j) if (x[j]=='<' || x[j]=='=' || x[j]=='>')
		{
			a[i]=x.substr(0,j);
			ti[i]=x[j];
			b[i]=x.substr(j+1);
		}
	}
	rek(0);
	cout<<an<<en;
	//cout<<mul(an,pot(inv10,20))<<en;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

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

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

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

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

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: 82ms
memory: 3608kb

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

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

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

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: 2ms
memory: 3680kb

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

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

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed