QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#192175#7512. Almost Prefix Concatenationucup-team1001TL 0ms3624kbC++141.3kb2023-09-30 13:49:222023-09-30 13:49:22

Judging History

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

  • [2023-09-30 13:49:22]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3624kb
  • [2023-09-30 13:49:22]
  • 提交

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...

output:


result: