QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341611#7858. Basic Equation SolvinggoodierAC ✓531ms4124kbC++175.5kb2024-02-29 20:05:382024-03-20 11:12:45

Judging History

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

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

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

input:

4
AB>CD
E<A
BC>FF
EF>F1

output:

23645065

result:

ok single line: '23645065'

Test #4:

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

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

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

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

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

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

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

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

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

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

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

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

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed