QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54095#2922. Word PuzzleBeevo#AC ✓3420ms50452kbC++231.2kb2022-10-06 21:01:112022-10-06 21:01:12

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-06 21:01:12]
  • 评测
  • 测评结果:AC
  • 用时:3420ms
  • 内存:50452kb
  • [2022-10-06 21:01:11]
  • 提交

answer

#include <bits/stdc++.h>

#define el '\n'
#define ll long long
#define ld long double

#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5 + 5, K = 50 + 5, M = 1e9 + 7;

int add(int a, int b) {
    a = (a % M + M) % M;
    b = (b % M + M) % M;

    return (a + b) % M;
}

int id = 1;
string s, t;
int dp[N][K];
int vis[N][K];

int solve(int i, int j) {
    if (i > s.size())
        return j == t.size();

    int &ret = dp[i][j];

    if (vis[i][j] == id)
        return ret;

    vis[i][j] = id;

    ret = solve(i + 1, j);

    if (j < t.size() && s[i] == t[j])
        ret = add(ret, solve(i + 1, j + 1));

    return ret;
}

void testCase() {
    cin >> s >> t;

    set<string> sts;
    for (int i = 0; i < t.size(); i++) {
        sts.insert(t);

        char c = t.back();

        t.pop_back();

        t = c + t;
    }

    int sol = 0;
    for (auto i: sts) {
        t = i;

        sol = add(sol, solve(0, 0));

        id++;
    }

    cout << sol;
}

signed main() {
    Beevo

    int T = 1;
//    cin >> T;

    while (T--)
        testCase();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3556kb

input:

x
x

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

x
y

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

aaaaaa
aaa

output:

20

result:

ok single line: '20'

Test #4:

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

input:

ababababab
abab

output:

50

result:

ok single line: '50'

Test #5:

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

input:

ababababab
abbba

output:

25

result:

ok single line: '25'

Test #6:

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

input:

abcdefg
cdefgab

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 101ms
memory: 50452kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

272473072

result:

ok single line: '272473072'

Test #8:

score: 0
Accepted
time: 3420ms
memory: 50424kb

input:

bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...

output:

282848711

result:

ok single line: '282848711'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba
babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb

output:

420104829

result:

ok single line: '420104829'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3784kb

input:

abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb
babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa

output:

766520634

result:

ok single line: '766520634'

Test #11:

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

input:

cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee
caaed

output:

47423

result:

ok single line: '47423'

Test #12:

score: 0
Accepted
time: 2801ms
memory: 50316kb

input:

babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...

output:

486637450

result:

ok single line: '486637450'

Test #13:

score: 0
Accepted
time: 2606ms
memory: 50252kb

input:

caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...

output:

936394934

result:

ok single line: '936394934'

Test #14:

score: 0
Accepted
time: 1925ms
memory: 50304kb

input:

dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...

output:

913565196

result:

ok single line: '913565196'

Test #15:

score: 0
Accepted
time: 126ms
memory: 50296kb

input:

vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...

output:

209906227

result:

ok single line: '209906227'

Test #16:

score: 0
Accepted
time: 1461ms
memory: 50388kb

input:

mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...

output:

214605073

result:

ok single line: '214605073'

Test #17:

score: 0
Accepted
time: 1780ms
memory: 50308kb

input:

akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...

output:

63161148

result:

ok single line: '63161148'

Test #18:

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

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

241224381

result:

ok single line: '241224381'

Test #19:

score: 0
Accepted
time: 1744ms
memory: 38616kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

718304672

result:

ok single line: '718304672'

Test #20:

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

input:

programming
rgg

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

aabbaa
aba

output:

12

result:

ok single line: '12'

Test #22:

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

input:

acca
acac

output:

0

result:

ok single line: '0'