QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636960 | #2922. Word Puzzle | enze114514# | AC ✓ | 670ms | 46984kb | C++20 | 1.8kb | 2024-10-13 04:27:27 | 2024-10-13 04:27:28 |
Judging History
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'