QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53767#2922. Word Puzzleabdelrahman001#AC ✓2716ms30764kbC++1.0kb2022-10-05 21:51:002022-10-05 21:51:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 21:51:01]
  • 评测
  • 测评结果:AC
  • 用时:2716ms
  • 内存:30764kb
  • [2022-10-05 21:51:00]
  • 提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
string s, t;
map<string, bool> vis;
int memo[N][55];
int solve(int i, int j) {
    if(j == t.size())
        return 1;
    if(i == s.size())
        return 0;
    int &ans = memo[i][j];
    if(~ans)
        return ans;
    ans = solve(i + 1, j);
    if(s[i] == t[j])
        ans = (ans + solve(i + 1, j + 1)) % mod;
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> s >> t;
    int ans = 0;
    for(int i = 0;i < t.size();i++) {
        string x = "";
        x += t.back();
        t.pop_back();
        t = x + t;
        if(vis[t])
            continue;
        vis[t] = true;
        memset(memo, -1, sizeof memo);
        ans = (ans + solve(0, 0)) % mod;
    }
    cout << ans;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 25208kb

input:

x
x

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 4ms
memory: 25208kb

input:

x
y

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 2ms
memory: 24984kb

input:

aaaaaa
aaa

output:

20

result:

ok single line: '20'

Test #4:

score: 0
Accepted
time: 5ms
memory: 25132kb

input:

ababababab
abab

output:

50

result:

ok single line: '50'

Test #5:

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

input:

ababababab
abbba

output:

25

result:

ok single line: '25'

Test #6:

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

input:

abcdefg
cdefgab

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 65ms
memory: 30704kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

272473072

result:

ok single line: '272473072'

Test #8:

score: 0
Accepted
time: 2716ms
memory: 30764kb

input:

bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...

output:

282848711

result:

ok single line: '282848711'

Test #9:

score: 0
Accepted
time: 53ms
memory: 25124kb

input:

baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba
babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb

output:

420104829

result:

ok single line: '420104829'

Test #10:

score: 0
Accepted
time: 55ms
memory: 25124kb

input:

abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb
babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa

output:

766520634

result:

ok single line: '766520634'

Test #11:

score: 0
Accepted
time: 4ms
memory: 25136kb

input:

cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee
caaed

output:

47423

result:

ok single line: '47423'

Test #12:

score: 0
Accepted
time: 2131ms
memory: 30724kb

input:

babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...

output:

486637450

result:

ok single line: '486637450'

Test #13:

score: 0
Accepted
time: 2226ms
memory: 30632kb

input:

caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...

output:

936394934

result:

ok single line: '936394934'

Test #14:

score: 0
Accepted
time: 1772ms
memory: 30724kb

input:

dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...

output:

913565196

result:

ok single line: '913565196'

Test #15:

score: 0
Accepted
time: 113ms
memory: 30728kb

input:

vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...

output:

209906227

result:

ok single line: '209906227'

Test #16:

score: 0
Accepted
time: 1374ms
memory: 30636kb

input:

mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...

output:

214605073

result:

ok single line: '214605073'

Test #17:

score: 0
Accepted
time: 1653ms
memory: 30652kb

input:

akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...

output:

63161148

result:

ok single line: '63161148'

Test #18:

score: 0
Accepted
time: 21ms
memory: 29340kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

241224381

result:

ok single line: '241224381'

Test #19:

score: 0
Accepted
time: 1238ms
memory: 29344kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

718304672

result:

ok single line: '718304672'

Test #20:

score: 0
Accepted
time: 11ms
memory: 25196kb

input:

programming
rgg

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 2ms
memory: 25020kb

input:

aabbaa
aba

output:

12

result:

ok single line: '12'

Test #22:

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

input:

acca
acac

output:

0

result:

ok single line: '0'