QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96703 | #2922. Word Puzzle | mariam | AC ✓ | 3522ms | 28940kb | C++17 | 2.7kb | 2023-04-15 04:52:59 | 2023-04-15 04:53:24 |
Judging History
answer
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
#include <unordered_set>
#include <queue>
#include <map>
#include <cmath>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <stdio.h>
#include <stack>
#include <list>
#include "complex"
#include <assert.h>
#define el '\n'
#define ll long long
#define ld long double
using namespace std;
//
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 1e5 + 5, mod = 1e9 + 7, MAX = 1e9 + 1, M = 1e5;
long double PI = 3.14159265358979323846;;
#define point complex<long double>
#define vec(a, b) b-a
#define dot(a, b) (long double)(conj(a)*b).real()
#define cross(a, b) (long double)(conj(a)*b).imag()
#define length(a) (hypot((a).imag(), (a).real()))
#define angle(a) atan2((a).imag(), (a).real())
int h, w;
//char a[201][201];
//int dx[] = {0, 0, -1, 1, 1, -1, -1, 1}, dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
//int dx[] = {-1, -1, 0, 0, 1, 1}, dy[] = {-1, 0, -1, 1, 0, 1};
//
//bool valid(int i, int j) {
// return (i < h && i >= 0 && j < w && j >= 0);
//}
//
//bool vis[201][201];
ll mul(ll a, ll b) {
return ((a % mod) * (b % mod)) % mod;
}
ll add(ll a, ll b) {
return ((a % mod) + (b % mod)) % mod;
}
ll sub(ll a, ll b) {
return ((((a + mod) % mod) - ((b + mod) % mod)) + mod) % mod;
}
ll fastpow(ll b, ll p) {
if (p == 0)
return 1;
if (p == 1) {
return b;
}
ll hp = fastpow(b, p / 2);
ll ans = ((hp % mod) * (hp % mod)) % mod;
if (p % 2) {
ans = (ans * b) % mod;
}
return ans % mod;
}
string s, p, np;
int dp[N][55], n;
int solve(int i, int j) {
if (i == s.size()) {
if (j == n)
return 1;
else
return 0;
}
int &ans = dp[i][j];
if (~ans)return ans;
ans = solve(i + 1, j);
if (j < n && s[i] == np[j])
ans = add(ans, solve(i + 1, j + 1));
return (ans % mod);
}
void m() {
cin >> s >> p;
n = p.size();
ll ans = 0;
np = p;
set<string> st;
for (int i = 0; i < n; ++i) {
st.insert(np);
np = np.back() + np.substr(0, n - 1);
}
for (auto i: st) {
memset(dp, -1, sizeof dp);
np = i;
ans = add(ans, solve(0, 0));
}
cout << ans % mod << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin>>t;
while (t--) {
m();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 24848kb
input:
x x
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 24868kb
input:
x y
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 3ms
memory: 24808kb
input:
aaaaaa aaa
output:
20
result:
ok single line: '20'
Test #4:
score: 0
Accepted
time: 4ms
memory: 24812kb
input:
ababababab abab
output:
50
result:
ok single line: '50'
Test #5:
score: 0
Accepted
time: 9ms
memory: 24800kb
input:
ababababab abbba
output:
25
result:
ok single line: '25'
Test #6:
score: 0
Accepted
time: 15ms
memory: 24892kb
input:
abcdefg cdefgab
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 78ms
memory: 28892kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
272473072
result:
ok single line: '272473072'
Test #8:
score: 0
Accepted
time: 3522ms
memory: 28840kb
input:
bbbabaaabbbbaabbbbaaabbaaabbbbaaabaababaabaaaaaabbbaabaabbbaababbbabbbbbbbabbaabbabbabbabaaaabbbaabbabbaaabbbbabababaabbabababaabaaabbaabaaaababbabbababaabbabbaaabbaabbbbbaaabaabababbbbbaaabbaaaaaabaabababbabbaaaabaabbbaaaababbabababbaabababbaabbbbaababaabbaaabaabaababababbaaaababbbbababbbbaabbbabab...
output:
282848711
result:
ok single line: '282848711'
Test #9:
score: 0
Accepted
time: 89ms
memory: 24856kb
input:
baabaabbbbbaabbbabaaaaabaaaaabaaabaabbaabaaabbaababbabbaaaabbabbabbaaaabbbabbbbbbaaabbaaababbbbaabba babaaabaaaaabaaabaabababbabbbbaaaabbabaabbb
output:
420104829
result:
ok single line: '420104829'
Test #10:
score: 0
Accepted
time: 116ms
memory: 24828kb
input:
abbbababcccbbaacacccacabaacaaaccbcabaaaaababcbabbcbbcacabababababccbccaacccabaccccabcaabababbacccccb babbbaabbabcacabaccccabcababababcccbaacbaacbcbaaaa
output:
766520634
result:
ok single line: '766520634'
Test #11:
score: 0
Accepted
time: 11ms
memory: 24892kb
input:
cecbcaacdeeeddbdcbeeebecdddcbdeeebcabcabcccebeddeaceeadeceaeadedacbccbddddbedddbcbcbdecbcbcdaebcedee caaed
output:
47423
result:
ok single line: '47423'
Test #12:
score: 0
Accepted
time: 2859ms
memory: 28900kb
input:
babbbbbabbbbbbbaaabaabaabbbbaabbbbaaaaabbaaabaabbbbaaaababbbaaabbbbbbabaaabbbaaabbbababbaaabbaaabaaaaaaaaababbbbbabbaaabbbabbaabbaaabbabbbaabbbaaaaaaabaaabaaaaabaaabbaababaabaaabbbaabaaabbbaabbbbaaabaabbabbaabbbbbababbbabbbabbbababbaaaabbababbaababaabababbbaaaabababbbbababbbbbbaabaabbababaaaababaaba...
output:
486637450
result:
ok single line: '486637450'
Test #13:
score: 0
Accepted
time: 2690ms
memory: 28848kb
input:
caaaacaababbaacbbacccbaccbcbabbcaabaacabbaabcbbacbcbbacabbacbaabcbccacacabaaaacaaaabccabaaababaacaacacacacbcacaaaaacbcbaaabcabcbacabacbccaabbbbaccbbbcbabccbacbcbcbbaacbabcbabbbbabbccccbbabaacaabbacabaccacbbcabaabaacbcabbabbbabcccacbcaabbcacaccbaacbbbbacccbccacacabccacbbaccabcacaabcabcbccbcccabacbbac...
output:
936394934
result:
ok single line: '936394934'
Test #14:
score: 0
Accepted
time: 2022ms
memory: 28816kb
input:
dbcdddaaadacdccceadccedbbccbabcebadacaebdabbcecaebbbeeddbadcddbebeccaccebeedeccdcbeebbcbddccbbeabeebdccadabeacbecdbdcbdcbadaccbaabaceaabddabcabeceaccbbdedddaabbbeeeaedbeebcebdaccdcdaddaeeecccccaedaceecabdcbaaaedaecbcedaceedadaeabeddcadbbeabadedbadedadeeaddacccdeacabbbeebcddaaaaddeccaeeccceddbaddbedd...
output:
913565196
result:
ok single line: '913565196'
Test #15:
score: 0
Accepted
time: 115ms
memory: 28860kb
input:
vyupeidnwqivhxkbpswxpzmeuiucitgwiwnmlxwdzjdjahahukhwuvbqrussinpdvnhhgkhfwjrqobseorqztwnlqiuzwnmwwpeyimnrauerxvfgtrjgynvwypqiopphlblpphprkqsuatvujhbdktoqkxiayrarcesuwinubtqbtuyvkfgvewgsajtozaovzbotbljodualzwloalmpbkzpdpklsgbbevjggjkagpdpojjzyaogywifkcozzgjorpkkhovpyqgqnkmvplzncifpxmlmgijjhvhvvfvjjput...
output:
209906227
result:
ok single line: '209906227'
Test #16:
score: 0
Accepted
time: 1370ms
memory: 28884kb
input:
mqjwsxbfvfgmjwgwxagrpurduavgmflksepsgtaiayxurcwvpfgbdfntmxebtwagtvenyjqgmltobdsegwzvarwuomfjzvehbrswxnwblaiybojuotivicvrdqzzzkcmsdbkbwqjsjfdjjclujrbvaqykpodcerjjxlztclrowuwdbnqhrxhgesyyknqoaiusoawhtcmmjacugidjabncvgolnapmdfsetkjswaxxoeavvajsfvrdhwabwsshkoteayjdrnsltjxqufsvawqffizqmrljenpkbuxsejqixao...
output:
214605073
result:
ok single line: '214605073'
Test #17:
score: 0
Accepted
time: 1674ms
memory: 28940kb
input:
akajzzsqdheiuzcfetnlncvavcdugmlwzokhuoonnzakehmazollpnfggivfpdrdxwtdcszyvuoseeunfrjmhukcjhnqzqbbnifkelbhychdecdtiaxpcsbovburhzselpfbxjyecxpgrsbzwvamtnhaprldukdevbfwyqkkdoetivnjorrfvwznuysuyyyoxxwxkrrnupouwrnfkroauahcywbgxjsunlizmsohqmttextvzfswbhdwgzrhprudwnmghkjsnrpyzisjvovsqabtyvqodztmjmgllaacnmbe...
output:
63161148
result:
ok single line: '63161148'
Test #18:
score: 0
Accepted
time: 36ms
memory: 27860kb
input:
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...
output:
241224381
result:
ok single line: '241224381'
Test #19:
score: 0
Accepted
time: 2056ms
memory: 27868kb
input:
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...
output:
718304672
result:
ok single line: '718304672'
Test #20:
score: 0
Accepted
time: 4ms
memory: 24796kb
input:
programming rgg
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 4ms
memory: 24896kb
input:
aabbaa aba
output:
12
result:
ok single line: '12'
Test #22:
score: 0
Accepted
time: 2ms
memory: 24892kb
input:
acca acac
output:
0
result:
ok single line: '0'