QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96409#2922. Word PuzzleAbdelrahman_K#AC ✓2912ms27844kbC++14984b2023-04-13 21:03:182023-04-13 21:06:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 21:06:19]
  • 评测
  • 测评结果:AC
  • 用时:2912ms
  • 内存:27844kb
  • [2023-04-13 21:03:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef long double ld;
#define F first
#define S second
const int N = 1e5 + 2, mod = 1e9 + 7;
const ld eps = 1e-6;
int grid[57][57];
typedef complex<ld> point;
#define X real()
#define Y imag()
string s, t;
int dp[N][50];
int add(int x, int y) {
    return (x + y) % mod;
}
int solve(int i, int j) {
    if (j == t.size())
        return 1;
    if (i == s.size())
        return 0;
    if (~dp[i][j])
        return dp[i][j];
    int val = solve(i + 1, j);
    if (s[i] == t[j])
        val = add(val, solve(i + 1, j + 1));
    return dp[i][j] = val;
}
int main() {
    cin >> s >> t;
    int ans = 0;
    set<string> st;
    for (int i = 0; i < t.size(); i++) {
        t = t.back() + t;
        t.pop_back();
        memset(dp, -1, sizeof dp);
        if (!st.count(t))
            ans = add(ans, solve(0, 0));
        st.insert(t);
    }
    cout << ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

x
x

output:

1

result:

ok single line: '1'

Test #2:

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

input:

x
y

output:

0

result:

ok single line: '0'

Test #3:

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

input:

aaaaaa
aaa

output:

20

result:

ok single line: '20'

Test #4:

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

input:

ababababab
abab

output:

50

result:

ok single line: '50'

Test #5:

score: 0
Accepted
time: 9ms
memory: 22972kb

input:

ababababab
abbba

output:

25

result:

ok single line: '25'

Test #6:

score: 0
Accepted
time: 17ms
memory: 22960kb

input:

abcdefg
cdefgab

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 120ms
memory: 27724kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

272473072

result:

ok single line: '272473072'

Test #8:

score: 0
Accepted
time: 2912ms
memory: 27732kb

input:

bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...

output:

282848711

result:

ok single line: '282848711'

Test #9:

score: 0
Accepted
time: 66ms
memory: 22980kb

input:

baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba
babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb

output:

420104829

result:

ok single line: '420104829'

Test #10:

score: 0
Accepted
time: 74ms
memory: 22988kb

input:

abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb
babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa

output:

766520634

result:

ok single line: '766520634'

Test #11:

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

input:

cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee
caaed

output:

47423

result:

ok single line: '47423'

Test #12:

score: 0
Accepted
time: 2339ms
memory: 27776kb

input:

babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...

output:

486637450

result:

ok single line: '486637450'

Test #13:

score: 0
Accepted
time: 2391ms
memory: 27768kb

input:

caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...

output:

936394934

result:

ok single line: '936394934'

Test #14:

score: 0
Accepted
time: 1856ms
memory: 27844kb

input:

dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...

output:

913565196

result:

ok single line: '913565196'

Test #15:

score: 0
Accepted
time: 103ms
memory: 27728kb

input:

vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...

output:

209906227

result:

ok single line: '209906227'

Test #16:

score: 0
Accepted
time: 1156ms
memory: 27784kb

input:

mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...

output:

214605073

result:

ok single line: '214605073'

Test #17:

score: 0
Accepted
time: 1407ms
memory: 27740kb

input:

akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...

output:

63161148

result:

ok single line: '63161148'

Test #18:

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

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

241224381

result:

ok single line: '241224381'

Test #19:

score: 0
Accepted
time: 1340ms
memory: 26668kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

718304672

result:

ok single line: '718304672'

Test #20:

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

input:

programming
rgg

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 6ms
memory: 22956kb

input:

aabbaa
aba

output:

12

result:

ok single line: '12'

Test #22:

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

input:

acca
acac

output:

0

result:

ok single line: '0'