QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#564906#7858. Basic Equation Solving1234567890#AC ✓176ms3820kbC++144.9kb2024-09-15 16:57:352024-10-14 18:03:09

Judging History

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

  • [2024-10-14 18:03:09]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:176ms
  • 内存:3820kb
  • [2024-09-15 16:57:35]
  • 评测
  • 测评结果:100
  • 用时:177ms
  • 内存:3852kb
  • [2024-09-15 16:57:35]
  • 提交

answer

/*
わんわん……わんだほーいっ☆
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
const int MOD=998244353;
inline int Add(int u,int v){return u+v>=MOD?u+v-MOD:u+v;}
inline int Sub(int u,int v){return u-v>=0?u-v:u-v+MOD;}
inline int Mul(int u,int v){return LL(u)*LL(v)%MOD;}
inline int add(int &u,int v){return u=Add(u,v);}
inline int sub(int &u,int v){return u=Sub(u,v);}
inline int mul(int &u,int v){return u=Mul(u,v);}
int QuickPow(int x,int p=MOD-2)
{
    int ans=1,base=x;
    while(p)
    {
        if(p&1)    mul(ans,base);
        mul(base,base);
        p>>=1;
    }
    return ans;
}
int rev[256],idx;
int N;
string s1[55],s2[55];
int equ[55];
Poly eq[55],le[55];
Poly G[55]; // for toposort
Poly leq[55],geq[55]; // for components links (leq/geq only)
Poly lnk[55]; // leq or geq
int deg[55],top[55];
int opt[55]; // -1 for uncertain char
int ans;
int fa[55];
int rid[55];
bool vis[55];
void makeSet(){for(int i=1;i<=idx;++i)	fa[i]=i,vis[i]=false,opt[i]=-1,G[i].clear(),leq[i].clear(),geq[i].clear(),lnk[i].clear(),deg[i]=0;}
int findSet(int x){return x==fa[x]?x:fa[x]=findSet(fa[x]);}
void unionSet(int x,int y)
{
	x=findSet(x),y=findSet(y);
	if(x==y)	return ;
	fa[y]=x;
}
bool topsort()
{
	queue<int> Q;
	for(int i=1;i<=idx;++i)	if(!deg[i])	Q.push(i);
	int ccnt=0;
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		top[u]=++ccnt;
		for(int v:G[u])	if(!--deg[v])	Q.push(v);
	}
	return ccnt==idx;
}
int cnt;
int a[55];
void span(int u)
{
	if(vis[u])	return ;
	vis[u]=true;
	if(opt[u]==-1)	a[++cnt]=u;
	for(int v:lnk[u])	span(v);
}
bool check(int S,int p,int d)
{
	p=a[p+1];
	int u=findSet(p);
	for(int x:leq[u])
	{
		int v=x;
		if(~rid[v])
		{
			if((S>>rid[v])&1)	return false;
		}
		else if(d>=opt[v])	return false;
	}
	for(int x:geq[u])
	{
		int v=x;
		if(~rid[v])
		{
			if(((S>>rid[v])&1)==0)	return false;
		}
		else if(d<=opt[v])	return false;
	}
	return true;
}
int calc()
{
	makeSet();
	for(int u=1;u<=idx;++u)	for(int v:eq[u])	unionSet(u,v);
	for(int i=1;i<=10;++i)
	{
		int u=findSet(i);
		if(~opt[u])	return 0;
		opt[u]=i-1;
	}
	for(int i=1;i<=idx;++i)
	{
		int u=findSet(i);
		if(opt[u]==-1)	continue;
		for(int p:le[i])
		{
			int v=findSet(p);
			if(opt[v]!=-1 && opt[v]<=opt[u])	return 0;
		}
	}
	for(int i=1;i<=idx;++i)
	{
		int u=findSet(i);
		for(int p:le[i])
		{
			int v=findSet(p);
			if(u==v)	return 0;
			G[v].push_back(u);
//			printf("%d %d\n",u,v);
			leq[u].push_back(v),geq[v].push_back(u);
			lnk[u].push_back(v),lnk[v].push_back(u);
			++deg[u];
		}
	}
	if(!topsort())	return 0;
	int ret=1;
	for(int p=1;p<=idx;++p)
	{
		if(findSet(p)!=p || vis[p])	continue;
		cnt=0;
		span(p);
		if(!cnt)	continue;
		sort(a+1,a+1+cnt,[&](int x,int y){return top[x]<top[y];});
		for(int i=1;i<=idx;++i)	rid[i]=-1;
		for(int i=1;i<=cnt;++i)	rid[a[i]]=i-1;
		static int f[1<<12];
		for(int S=0;S<(1<<cnt);++S)	f[S]=0;
		f[0]=1;
		for(int d=0;d<10;++d)
		{
			for(int i=0;i<cnt;++i)
			{
				for(int S=(1<<cnt)-1;~S;--S)
				{
					if(!f[S])	continue;
					if((S>>i)&1)	continue;
					if(check(S,i,d))	add(f[S|(1<<i)],f[S]);
				}
			}
		}
		mul(ret,f[(1<<cnt)-1]);
	}
	return ret;
}
void dfs(int u)
{
	if(u>N)	return void(add(ans,calc()));
	int len=s1[u].length();
	if(equ[u])
	{
		for(int i=0;i<len;++i)
		{
			int x=rev[(int)s1[u][i]],y=rev[(int)s2[u][i]];
			eq[x].push_back(y),eq[y].push_back(x);
		}
		dfs(u+1);
		for(int i=0;i<len;++i)
		{
			int x=rev[(int)s1[u][i]],y=rev[(int)s2[u][i]];
			eq[x].pop_back(),eq[y].pop_back();
		}
	}
	else
	{
		for(int i=0;i<len;++i)
		{
			if(i)
			{
				int x=rev[(int)s1[u][i-1]],y=rev[(int)s2[u][i-1]];
				eq[x].push_back(y),eq[y].push_back(x);
			}
			int x=rev[(int)s1[u][i]],y=rev[(int)s2[u][i]];
			le[x].push_back(y);
			dfs(u+1);
			le[x].pop_back();
		}
		for(int i=0;i<len;++i)
		{
			if(i)
			{
				int x=rev[(int)s1[u][i-1]],y=rev[(int)s2[u][i-1]];
				eq[x].pop_back(),eq[y].pop_back();
			}
		}
	}
}
int main(){
	for(int i='0';i<='9';++i)	rev[i]=++idx;
	for(int i='A';i<='Z';++i)	rev[i]=++idx;
	cin>>N;
	for(int i=1;i<=N;++i)
	{
		string s;
		cin>>s;
		int len=int(s.length());
		for(int j=0;j<len;++j)
		{
			if(s[j]=='=' || s[j]=='<' || s[j]=='>')
			{
				s1[i]=s.substr(0,j),s2[i]=s.substr(j+1,len);
				if(s[j]=='>')	swap(s1[i],s2[i]);
				if(s1[i].length()^s2[i].length())
				{
					while(s1[i].length()<s2[i].length())	s1[i]="0"+s1[i];
					while(s1[i].length()>s2[i].length())	s2[i]="0"+s2[i];
				}
//				cout<<s1[i]<<" "<<s2[i]<<endl;
				equ[i]=int(s[j]=='=');
			}
		}
	}
	dfs(1);
	cout<<ans<<endl;
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

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

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

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

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: 176ms
memory: 3596kb

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: 156ms
memory: 3616kb

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

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

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

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

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

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

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

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed