QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636960#2922. Word Puzzleenze114514#AC ✓670ms46984kbC++201.8kb2024-10-13 04:27:272024-10-13 04:27:28

Judging History

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

  • [2024-10-13 04:27:28]
  • 评测
  • 测评结果:AC
  • 用时:670ms
  • 内存:46984kb
  • [2024-10-13 04:27:27]
  • 提交

answer

    #include <bits/stdc++.h>

    using namespace std;
    using ll = long long;
    using ld = long double;
    #define int long long

    #define pb push_back

    const ld pi = 3.14159265358979323846;
    const int mod = 1000000007;
    const ll INF = 1e18;

    string p, S, s;

    template<typename T>
    T chmax(T a, T b) {
        return a > b ? a : b;
    }

    template<typename T>
    T chmin(T a, T b) {
        return a > b ? b : a;
    }

    const int N = (int) 1e5 + 5, M = N * 2;

    int ans = 0;
    int f[N][55];
    inline void dp() {
        int n = p.length(), m = s.length();
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m + 1; ++j) {
                f[i][j] = 0;
            }
        }
        f[0][0] = 1;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j != m && p[i] == s[j]) {
                    f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;
                }
                f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
            }
        }

        ans = (ans + f[n][m]) % mod;
    }

    map<string, int> mp;

    void solve() {
        cin >> p >> S;
        for (int i = 0; i < S.length(); ++i) {
            s = S.substr(i, S.length() - i) + S.substr(0, i);
            if (mp[s]) continue;
            mp[s] = 1;
    //        cout << s << '\n';
            dp();
        }

        cout << ans << '\n';
    }

    signed main() {
        // freopen(".in", "r", stdin);
        // freopen(".out", "w", stdout);

        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int t = 1;
    //    cin >> t;

        while (t--) {
            solve();
        }

        return 0;
    }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

x
x

output:

1

result:

ok single line: '1'

Test #2:

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

input:

x
y

output:

0

result:

ok single line: '0'

Test #3:

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

input:

aaaaaa
aaa

output:

20

result:

ok single line: '20'

Test #4:

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

input:

ababababab
abab

output:

50

result:

ok single line: '50'

Test #5:

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

input:

ababababab
abbba

output:

25

result:

ok single line: '25'

Test #6:

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

input:

abcdefg
cdefgab

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 12ms
memory: 46680kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

272473072

result:

ok single line: '272473072'

Test #8:

score: 0
Accepted
time: 670ms
memory: 46984kb

input:

bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...

output:

282848711

result:

ok single line: '282848711'

Test #9:

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

input:

baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba
babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb

output:

420104829

result:

ok single line: '420104829'

Test #10:

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

input:

abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb
babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa

output:

766520634

result:

ok single line: '766520634'

Test #11:

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

input:

cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee
caaed

output:

47423

result:

ok single line: '47423'

Test #12:

score: 0
Accepted
time: 564ms
memory: 46720kb

input:

babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...

output:

486637450

result:

ok single line: '486637450'

Test #13:

score: 0
Accepted
time: 554ms
memory: 46948kb

input:

caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...

output:

936394934

result:

ok single line: '936394934'

Test #14:

score: 0
Accepted
time: 520ms
memory: 46684kb

input:

dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...

output:

913565196

result:

ok single line: '913565196'

Test #15:

score: 0
Accepted
time: 56ms
memory: 46712kb

input:

vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...

output:

209906227

result:

ok single line: '209906227'

Test #16:

score: 0
Accepted
time: 480ms
memory: 46944kb

input:

mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...

output:

214605073

result:

ok single line: '214605073'

Test #17:

score: 0
Accepted
time: 567ms
memory: 46756kb

input:

akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...

output:

63161148

result:

ok single line: '63161148'

Test #18:

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

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

241224381

result:

ok single line: '241224381'

Test #19:

score: 0
Accepted
time: 497ms
memory: 36508kb

input:

abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...

output:

718304672

result:

ok single line: '718304672'

Test #20:

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

input:

programming
rgg

output:

2

result:

ok single line: '2'

Test #21:

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

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'