QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#192175 | #7512. Almost Prefix Concatenation | ucup-team1001 | TL | 0ms | 3624kb | C++14 | 1.3kb | 2023-09-30 13:49:22 | 2023-09-30 13:49:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
struct node
{
int cur1,cur2,ok,now;
bool operator <(node x)const
{
if(cur1!=x.cur1)
return cur1<x.cur1;
if(cur2!=x.cur2)
return cur2<x.cur2;
if(ok!=x.ok)
return ok<x.ok;
if(now!=x.now)
return now<x.now;
}
bool operator==(node x) const
{
return cur1==x.cur1&&cur2==x.cur2&&ok==x.ok&&now==x.now;
}
};
map<node,long long> save;
string s1,s2;
long long dfs(int cur1,int cur2,int ok,int now)
{
if(save[{cur1,cur2,ok,now}])
return save[{cur1,cur2,ok,now}];
if(cur1==s1.size())
{
if(cur2)
{
now++;
cur2=0;
}
return save[{cur1,cur2,ok,now}]=now*now%mod;
}
if(cur2==s2.size())
return save[{cur1,cur2,ok,now}]=dfs(cur1,0,0,now+1);
if(s2[cur2]==s1[cur1])
{
if(cur2)
return save[{cur1,cur2,ok,now}]=(dfs(cur1+1,cur2+1,ok,now)+dfs(cur1,0,0,now+1))%mod;
else
return save[{cur1,cur2,ok,now}]=dfs(cur1+1,cur2+1,ok,now);
}
if(s2[cur2]!=s1[cur1])
{
if(!ok&&cur2)
return save[{cur1,cur2,ok,now}]=(dfs(cur1+1,cur2+1,1,now)+dfs(cur1,0,0,now+1))%mod;
else if(ok)
return save[{cur1,cur2,ok,now}]=dfs(cur1,0,0,now+1);
else
return save[{cur1,cur2,ok,now}]=dfs(cur1+1,cur2+1,1,now);
}
}
int main()
{
//freopen("1.in","r",stdin);
cin>>s1>>s2;
cout<<dfs(0,0,0,0);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: -100
Time Limit Exceeded
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...