QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289544#7858. Basic Equation Solvingucup-team266AC ✓35ms4028kbC++145.9kb2023-12-23 18:16:442024-03-20 11:12:19

Judging History

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

  • [2024-03-20 11:12:19]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:35ms
  • 内存:4028kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2023-12-23 18:16:45]
  • 评测
  • 测评结果:100
  • 用时:36ms
  • 内存:4064kb
  • [2023-12-23 18:16:44]
  • 提交

answer

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int mask[15][26];
int n;
vector <pair<string,string> > vec;
int ge[15][26][26],gl[15][26][26];
bool Typ(char x)
{
	if('0'<=x&&x<='9') return 0;
	return 1;
}
int fa[26];
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x!=y) fa[x]=y;
}
bool cut(int dep)
{
	for(int i=0;i<26;i++)
	{
		if(!mask[dep][i]) return 1;
		for(int j=i+1;j<26;j++) if((ge[dep][i][j]>0)+(gl[dep][i][j]>0)+(gl[dep][j][i]>0)>=2) return 1;
	}
	return 0;	
}
int rmask[26];
vector <int> g[26];
int id[26],ok[10];
int adj[1<<11],dp[2][1<<11];
int calc(vector <int> v)
{
	int m=v.size();
	memset(id,-1,sizeof(id));
	memset(ok,0,sizeof(ok));
	for(int i=0;i<(1<<m);i++) adj[i]=dp[0][i]=dp[1][i]=0;
	for(int i=0;i<v.size();i++) 
	{
		id[v[i]]=i;
		for(int j=0;j<10;j++) if(rmask[v[i]]&(1<<j))  ok[j]|=(1<<i);
	}
//	for(int j=0;j<10;j++) cout<<ok[j]<<" ";
//	cout<<"\n";
	for(int i=0;i<v.size();i++) for(int j=0;j<g[v[i]].size();j++) assert(id[g[v[i]][j]]!=-1),adj[1<<i]|=(1<<(id[g[v[i]][j]]));
//	for(int i=0;i<m;i++) cout<<adj[1<<i]<<" ";
//	cout<<"\n";
	for(int dim=0;dim<m;dim++) for(int j=0;j<(1<<m);j++) if(j&(1<<dim)) adj[j]|=adj[j^(1<<dim)];
	dp[0][(1<<m)-1]=1;
	int nw=0;
	for(int dig=0;dig<10;dig++)
	{
		nw^=1;
//		assert(ok[dig]==(1<<m)-1);
		for(int j=0;j<(1<<m);j++) dp[nw][j]=0;
		for(int j=0;j<(1<<m);j++) if(dp[nw^1][j])
		{
			int S=j&ok[dig]&(((1<<m)-1)^adj[j]);
			for(int T=S;;T=(T-1)&S)
			{
				dp[nw][j^T]=(dp[nw][j^T]+dp[nw^1][j])%mod;
				
				if(!T) break;
			}
		}
	}
//	cout<<v.size()<<" "<<v[0]<<" "<<dp[nw][0]<<"\n";
	return dp[nw][0];
}
int ans=0;
void calc(int dep)
{
	for(int i=0;i<26;i++) fa[i]=i;
	for(int i=0;i<26;i++) for(int j=i+1;j<26;j++) if(ge[dep][i][j]||ge[dep][j][i]) merge(i,j);
	for(int i=0;i<26;i++) rmask[i]=(find(i)==i?((1<<10)-1):-1);
	for(int i=0;i<26;i++) rmask[find(i)]&=mask[dep][i];
	for(int i=0;i<26;i++) if(rmask[i]!=-1&&!rmask[i]) return;
	int nowans=1;
	for(int i=0;i<26;i++) g[i].clear();
	int flg=0;
	for(int i=0;i<26;i++) for(int j=0;j<26;j++) if(gl[dep][i][j]) flg|=(find(i)==find(j)),g[find(i)].pb(find(j));
	for(int i=0;i<26;i++) for(int j=0;j<26;j++) if(gl[dep][i][j]) merge(i,j);
//	for(int i=0;i<6;i++) cout<<mask[dep][i]<<" ";
//	cout<<"\n";
//	for(int i=0;i<6;i++)
//	{
//		for(int j=0;j<6;j++) cout<<ge[dep][i][j]<<" ";
//		cout<<"\n";
//	}
//	cout<<"\n";
//	for(int i=0;i<6;i++)
//	{
//		for(int j=0;j<6;j++) cout<<gl[dep][i][j]<<" ";
//		cout<<"\n";
//	}
	for(int i=0;i<26;i++) if(find(i)==i)
	{
		vector <int> v;
		for(int j=0;j<26;j++) if(rmask[j]!=-1&&find(j)==i) v.pb(j);//,cout<<j<<" ";
//		cout<<"\n"; 
		int x=calc(v);
//		cout<<x<<"\n";
		nowans=1LL*nowans*x%mod;
	}
//	system("pause");
	ans=(ans+nowans)%mod;
}
void cpy(int dep)
{
	for(int i=0;i<26;i++)
	{
		mask[dep+1][i]=mask[dep][i];
		for(int j=0;j<26;j++) ge[dep+1][i][j]=ge[dep][i][j],gl[dep+1][i][j]=gl[dep][i][j];
	}
}
void dfs(int dep)
{
	if(cut(dep)) return;
	if(dep==vec.size())
	{
		calc(dep);
		return;
	}
	
	string a=vec[dep].fi,b=vec[dep].se; 
	for(int s=0;s<a.size();s++)
	{
		cpy(dep);
		for(int i=0;i<s;i++) if(a[i]!=b[i])
		{
			if(Typ(a[i])==0&&Typ(b[i])==0) return; 
			if(Typ(a[i])==1&&Typ(b[i])==1) ge[dep+1][a[i]-'A'][b[i]-'A']=ge[dep+1][b[i]-'A'][a[i]-'A']=1;
			if(Typ(a[i])==0&&Typ(b[i])==1) mask[dep+1][b[i]-'A']&=(1<<(a[i]-'0'));
			if(Typ(a[i])==1&&Typ(b[i])==0) mask[dep+1][a[i]-'A']&=(1<<(b[i]-'0'));
		}
		if(Typ(a[s])==0&&Typ(b[s])==0)
		{
			if(a[s]>b[s]) return;
			if(a[s]<b[s]) dfs(dep+1);
		}
		else if(Typ(a[s])==0&&Typ(b[s])==1)
		{
			for(int j=0;j<=a[s]-'0';j++) if(mask[dep+1][b[s]-'A']&(1<<j)) mask[dep+1][b[s]-'A']^=(1<<j);
			dfs(dep+1);
		}
		else if(Typ(a[s])==1&&Typ(b[s])==0)
		{
			swap(a[s],b[s]);
			for(int j=a[s]-'0';j<=9;j++) if(mask[dep+1][b[s]-'A']&(1<<j)) mask[dep+1][b[s]-'A']^=(1<<j);
			swap(a[s],b[s]);
			dfs(dep+1);
			
		}
		else
		{
			int u=a[s]-'A',v=b[s]-'A';
			if(u!=v)
			{
				gl[dep+1][u][v]=1;
				dfs(dep+1);
//				gl[dep+1][u][v]--;
			}
		}
	}
}
void solve()
{
	cin>>n;
	for(int i=0;i<26;i++) mask[0][i]=(1<<10)-1;
	while(n--)
	{
		string s;
		cin>>s;
		string a="",b="";
		char op;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='<'||s[i]=='='||s[i]=='>') 
			{
				op=s[i];
				break;
			}
			a+=s[i];
		}
		for(int i=s.size()-1;i>=0;i--)
		{
			if(s[i]=='<'||s[i]=='='||s[i]=='>') 
			{
				op=s[i];
				break;
			}
			b=s[i]+b;
		}
		while(a.size()<b.size()) a='0'+a;
		while(a.size()>b.size()) b='0'+b;
		
		if(op=='=')
		{
			for(int i=0;i<a.size();i++) if(a[i]!=b[i])
			{
				if(Typ(a[i])==0&&Typ(b[i])==0)
				{
					cout<<"0\n";
					return;
				}
				if(Typ(a[i])==1&&Typ(b[i])==1) ge[0][a[i]-'A'][b[i]-'A']=ge[0][b[i]-'A'][a[i]-'A']=1;
				if(Typ(a[i])==0&&Typ(b[i])==1) mask[0][b[i]-'A']&=(1<<(a[i]-'0'));
				if(Typ(b[i])==0&&Typ(a[i])==1) mask[0][a[i]-'A']&=(1<<(b[i]-'0'));
			}
			continue;
		}
		if(op=='>') swap(a,b);
//		cout<<a<<" "<<b<<"\n";
		vec.pb(mp(a,b));
	}
	dfs(0);
	cout<<ans<<"\n";
	
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

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

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

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

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: 35ms
memory: 3660kb

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: 27ms
memory: 4028kb

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

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

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

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

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

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

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

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed