QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270858#2922. Word PuzzlePetroTarnavskyi#AC ✓395ms32912kbC++171.3kb2023-12-01 16:42:582023-12-01 16:42:59

Judging History

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

  • [2023-12-01 16:42:59]
  • 评测
  • 测评结果:AC
  • 用时:395ms
  • 内存:32912kb
  • [2023-12-01 16:42:58]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1'000'000'007;

void updAdd(int& a, int b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}

int ans = 0;
const int N = 100'447;
const int M = 74;

int dp[N][M];


void f(string s, string t)
{
	int n = SZ(s);
	int m = SZ(t);
	
	FOR (i, 0, n + 1)
		FOR (j, 0, m + 1)
			dp[i][j] = 0;
	dp[0][0] = 1;
	FOR (i, 0, n)
	{
		FOR (j, 0, m + 1)
		{
			if (j != m && s[i] == t[j])
				updAdd(dp[i + 1][j + 1], dp[i][j]);
			updAdd(dp[i + 1][j], dp[i][j]); 
		}
	}
	updAdd(ans, dp[n][m]);
}


int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	string s;
	string t;
	cin >> s >> t;
	
	set<string> was;
	
	FOR (i, 0, SZ(t))
	{
		string t2 = t.substr(i, SZ(t) - i);
		t2 += t.substr(0, i);
		if (!was.count(t2))
		{
			was.insert(t2);
			f(s, t2);
		}
		
	}
	cout << ans << '\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

x
x

output:

1

result:

ok single line: '1'

Test #2:

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

input:

x
y

output:

0

result:

ok single line: '0'

Test #3:

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

input:

aaaaaa
aaa

output:

20

result:

ok single line: '20'

Test #4:

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

input:

ababababab
abab

output:

50

result:

ok single line: '50'

Test #5:

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

input:

ababababab
abbba

output:

25

result:

ok single line: '25'

Test #6:

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

input:

abcdefg
cdefgab

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 7ms
memory: 32676kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

272473072

result:

ok single line: '272473072'

Test #8:

score: 0
Accepted
time: 395ms
memory: 32684kb

input:

bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...

output:

282848711

result:

ok single line: '282848711'

Test #9:

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

input:

baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba
babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb

output:

420104829

result:

ok single line: '420104829'

Test #10:

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

input:

abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb
babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa

output:

766520634

result:

ok single line: '766520634'

Test #11:

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

input:

cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee
caaed

output:

47423

result:

ok single line: '47423'

Test #12:

score: 0
Accepted
time: 323ms
memory: 32620kb

input:

babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...

output:

486637450

result:

ok single line: '486637450'

Test #13:

score: 0
Accepted
time: 334ms
memory: 32740kb

input:

caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...

output:

936394934

result:

ok single line: '936394934'

Test #14:

score: 0
Accepted
time: 320ms
memory: 32684kb

input:

dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...

output:

913565196

result:

ok single line: '913565196'

Test #15:

score: 0
Accepted
time: 30ms
memory: 32912kb

input:

vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...

output:

209906227

result:

ok single line: '209906227'

Test #16:

score: 0
Accepted
time: 303ms
memory: 32684kb

input:

mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...

output:

214605073

result:

ok single line: '214605073'

Test #17:

score: 0
Accepted
time: 363ms
memory: 32856kb

input:

akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...

output:

63161148

result:

ok single line: '63161148'

Test #18:

score: 0
Accepted
time: 8ms
memory: 26056kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

241224381

result:

ok single line: '241224381'

Test #19:

score: 0
Accepted
time: 277ms
memory: 25888kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

718304672

result:

ok single line: '718304672'

Test #20:

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

input:

programming
rgg

output:

2

result:

ok single line: '2'

Test #21:

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

input:

aabbaa
aba

output:

12

result:

ok single line: '12'

Test #22:

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

input:

acca
acac

output:

0

result:

ok single line: '0'