QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#341611 | #7858. Basic Equation Solving | goodier | AC ✓ | 551ms | 4128kb | C++17 | 5.5kb | 2024-02-29 20:05:38 | 2024-02-29 20:05:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int N = 55, M = 11, T = 210;
vector <int> G1[N], G2[N], G3[N], G4[N], G5[N];
string str, str1[N], str2[N];
int op[N], n, id[T], idx, fa[N], v[N], a[N], cnt, dig[N], pos[N], b[N], totb, deg[N];
ll f[1 << M], ans;
int get(int x)
{
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
void merge(int x, int y)
{
x = get(x), y = get(y);
if(x != y) fa[y] = x;
}
void dfs3(int x)
{
if(v[x]) return;
v[x] = 1;
if(dig[x] == -1) a[cnt++] = x;
for(auto& y : G3[x]) dfs3(y);
}
int valid(int i, int j, int k)
{
int x = get(a[k]);
for(auto& y : G4[x])
{
if(pos[y] != -1)
{
if(((j >> pos[y]) & 1) == 1) return 0;
}
else if(i >= dig[y]) return 0;
}
for(auto& y : G5[x])
{
if(pos[y] != -1)
{
if(((j >> pos[y]) & 1) == 0) return 0;
}
else if(i <= dig[y]) return 0;
}
return 1;
}
int toposort()
{
queue <int> q;
for(int i = 1; i <= idx; i++) deg[i] = 0;
for(int x = 1; x <= idx; x++)
{
for(auto& y : G5[x])
{
deg[y]++;
}
}
for(int x = 1; x <= idx; x++) if(!deg[x]) q.push(x);
totb = 0;
while(!q.empty())
{
int x = q.front(); q.pop();
b[x] = ++totb;
for(auto& y : G5[x])
{
if(!--deg[y]) q.push(y);
}
}
if(totb < idx) return 0;
return 1;
}
bool cmp1(int x, int y)
{
return b[x] < b[y];
}
void dp()
{
for(int i = 1; i <= idx; i++) fa[i] = i, v[i] = 0, G3[i].clear(), G4[i].clear(), G5[i].clear(), dig[i] = -1;
for(int x = 1; x <= idx; x++)
{
for(auto& y : G1[x]) merge(x, y);
}
for(int i = 1; i <= 10; i++)
{
if(dig[get(i)] != -1) return;
dig[get(i)] = i - 1;
}
for(int i = 1; i <= idx; i++)
{
int x = get(i);
if(dig[x] == -1) continue;
for(auto& y : G2[i])
{
if(dig[get(y)] != -1 && dig[x] > dig[get(y)]) return;
}
}
for(int x = 1; x <= idx; x++)
{
for(auto& y : G2[x])
{
if(get(x) == get(y)) return;
//cout << x << " " << y << endl;
G3[get(x)].push_back(get(y)), G3[get(y)].push_back(get(x));
G4[get(x)].push_back(get(y)), G5[get(y)].push_back(get(x));
}
}
if(!toposort()) return;
ll res = 1ll;
for(int st = 1; st <= idx; st++)
{
if(v[st] || get(st) != st) continue;
cnt = 0;
dfs3(st);
if(!cnt) continue;
sort(a, a + cnt, cmp1);
for(int i = 1; i <= idx; i++) pos[i] = -1;
for(int i = 0; i < cnt; i++) pos[a[i]] = i;
for(int j = 0; j < 1 << cnt; j++) f[j] = 0;
f[0] = 1;
for(int i = 0; i < 10; i++)
{
for(int k = 0; k < cnt; k++)
{
for(int j = (1 << cnt) - 1; j >= 0; j--)
{
if((((j >> k) & 1) == 0) && valid(i, j, k) && f[j])
{
f[j | (1 << k)] += f[j];
if(f[j | (1 << k)] >= MOD) f[j | (1 << k)] -= MOD;
}
}
}
}
res = res * f[(1 << cnt) - 1] % MOD;
}
ans = (ans + res) % MOD;
}
void dfslcp(int k)
{
if(k > n)
{
dp();
return;
}
int len = str1[k].length();
if(op[k] == 1)
{
for(int i = 0; i < len; i++)
{
//cout << id[str1[k][i]] << " " << id[str2[k][i]] << endl;
G1[id[str1[k][i]]].push_back(id[str2[k][i]]);
G1[id[str2[k][i]]].push_back(id[str1[k][i]]);
}
dfslcp(k + 1);
for(int i = len - 1; i >= 0; i--)
{
G1[id[str1[k][i]]].pop_back();
G1[id[str2[k][i]]].pop_back();
}
}
else
{
for(int i = 0; i < len; i++) //lcplen=i
{
if(i > 0) G1[id[str1[k][i - 1]]].push_back(id[str2[k][i - 1]]);
G2[id[str1[k][i]]].push_back(id[str2[k][i]]);
//cout << id[str1[k][i]] << " " << id[str2[k][i]] << endl;
dfslcp(k + 1);
G2[id[str1[k][i]]].pop_back();
}
for(int i = len - 2; i >= 0; i--) //lcplen=i
{
G1[id[str1[k][i]]].pop_back();
}
}
}
int main()
{
//freopen("data.in", "r", stdin);
//freopen("/home/zhangenbo/contest/random/data.out", "w", stdout);
for(int i = '0'; i <= '9'; i++) id[i] = ++idx;
for(int i = 'A'; i <= 'Z'; i++) id[i] = ++idx;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
cin >> str;
int len = str.length();
for(int j = 1; j < len - 1; j++)
{
if(str[j] == '<' || str[j] == '>' || str[j] == '=')
{
str1[i] = str.substr(0, j);
str2[i] = str.substr(j + 1, len - j - 1);
if(str[j] == '>') swap(str1[i], str2[i]);
if(str[j] == '=') op[i] = 1;
break;
}
}
}
for(int i = 1; i <= n; i++)
{
while(str1[i].length() < str2[i].length()) str1[i] = "0" + str1[i];
while(str2[i].length() < str1[i].length()) str2[i] = "0" + str2[i];
}
//cout << str1[1] << " " << str2[1] << endl;
dfslcp(1);
printf("%lld\n", ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4064kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3764kb
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: 3820kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 7ms
memory: 3836kb
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: 18ms
memory: 4076kb
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: 19ms
memory: 3828kb
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: 551ms
memory: 4108kb
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: 531ms
memory: 4128kb
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: 4068kb
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: 3808kb
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: 4112kb
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: 3828kb
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: 3888kb
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: 3800kb
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: 4108kb
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: 1ms
memory: 3804kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4112kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3816kb
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: 3824kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed