QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#53805 | #2922. Word Puzzle | Silverhorse7 | AC ✓ | 3617ms | 49924kb | C++ | 859b | 2022-10-05 22:53:26 | 2022-10-05 22:53:27 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int N = 1e5 + 1, M = 51, mod = 1000000007;
int dp[N][M];
string s, t;
int n, m;
int solve(int p1, int p2) {
int &ret = dp[p1][p2];
if (~ret)return ret;
if (p1 == n) {
return p2 == m;
}
ret = solve(p1 + 1, p2);
if (p2 < m and s[p1] == t[p2])
ret = (ret + solve(p1 + 1, p2 + 1)) % mod;
return ret;
}
signed main() {
memset(dp, -1, sizeof dp);
cin >> s >> t;
vector<int> pos;
int cnt = 0;
n = s.size(), m = t.size();
map<string, int> found;
for (int i = 0; i < m; i++) {
memset(dp, -1, sizeof dp);
if (!found[t])
cnt = (cnt + solve(0, 0)) % mod;
found[t] = 1;
t = t.back() + t;
t.pop_back();
}
cout << cnt << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 43472kb
input:
x x
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 17ms
memory: 43476kb
input:
x y
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 27ms
memory: 43444kb
input:
aaaaaa aaa
output:
20
result:
ok single line: '20'
Test #4:
score: 0
Accepted
time: 24ms
memory: 43388kb
input:
ababababab abab
output:
50
result:
ok single line: '50'
Test #5:
score: 0
Accepted
time: 32ms
memory: 43448kb
input:
ababababab abbba
output:
25
result:
ok single line: '25'
Test #6:
score: 0
Accepted
time: 32ms
memory: 43460kb
input:
abcdefg cdefgab
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 310ms
memory: 49856kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
272473072
result:
ok single line: '272473072'
Test #8:
score: 0
Accepted
time: 3617ms
memory: 49840kb
input:
bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...
output:
282848711
result:
ok single line: '282848711'
Test #9:
score: 0
Accepted
time: 210ms
memory: 43384kb
input:
baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb
output:
420104829
result:
ok single line: '420104829'
Test #10:
score: 0
Accepted
time: 245ms
memory: 43568kb
input:
abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa
output:
766520634
result:
ok single line: '766520634'
Test #11:
score: 0
Accepted
time: 33ms
memory: 43548kb
input:
cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee caaed
output:
47423
result:
ok single line: '47423'
Test #12:
score: 0
Accepted
time: 2980ms
memory: 49824kb
input:
babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...
output:
486637450
result:
ok single line: '486637450'
Test #13:
score: 0
Accepted
time: 3153ms
memory: 49844kb
input:
caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...
output:
936394934
result:
ok single line: '936394934'
Test #14:
score: 0
Accepted
time: 2766ms
memory: 49924kb
input:
dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...
output:
913565196
result:
ok single line: '913565196'
Test #15:
score: 0
Accepted
time: 270ms
memory: 49700kb
input:
vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...
output:
209906227
result:
ok single line: '209906227'
Test #16:
score: 0
Accepted
time: 3012ms
memory: 49772kb
input:
mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...
output:
214605073
result:
ok single line: '214605073'
Test #17:
score: 0
Accepted
time: 3598ms
memory: 49832kb
input:
akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...
output:
63161148
result:
ok single line: '63161148'
Test #18:
score: 0
Accepted
time: 67ms
memory: 48188kb
input:
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...
output:
241224381
result:
ok single line: '241224381'
Test #19:
score: 0
Accepted
time: 1814ms
memory: 48268kb
input:
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...
output:
718304672
result:
ok single line: '718304672'
Test #20:
score: 0
Accepted
time: 20ms
memory: 43480kb
input:
programming rgg
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 29ms
memory: 43444kb
input:
aabbaa aba
output:
12
result:
ok single line: '12'
Test #22:
score: 0
Accepted
time: 23ms
memory: 43556kb
input:
acca acac
output:
0
result:
ok single line: '0'