Task: | String padding |
Sender: | Rasse |
Submission time: | 2024-11-04 22:23:37 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.01 s | details |
#8 | ACCEPTED | 0.01 s | details |
#9 | ACCEPTED | 0.01 s | details |
#10 | ACCEPTED | 0.01 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.01 s | details |
#15 | ACCEPTED | 0.01 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.01 s | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 32 | for (int i = 0; i < s.size(); i++) | ~~^~~~~~~~~~ input/code.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 39 | while (r < s.size() && s[l] == s[r]) | ~~^~~~~~~~~~ input/code.cpp:58:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 58 | while (r < s.size() && s[l] == s[r]) | ~~^~~~~~~~~~ input/code.cpp:68:25: warning: comparison of integer expressions of d...
Code
#include <iostream> #include <vector> #include <array> #include <string> #include <algorithm> #include <numeric> #include <unordered_map> #include <unordered_set> #include <set> #include <queue> #include <climits> #include <cmath> #include <functional> #include <type_traits> #include <bitset> #include <fstream> #define int long long using namespace std; int mod = 1000000007; void solve() { int n; string s; cin >> n >> s; vector<int> zArr(s.size()); vector<int> res; int l = 0, r = 0; for (int i = 0; i < s.size(); i++) { if (i > r) { // Use naive r = i; l = 0; while (r < s.size() && s[l] == s[r]) { l++; r++; } r--; l = i; zArr[i] = r-i+1; } else { if (zArr[i-l] < r-i+1) { zArr[i] = zArr[i-l]; } else { l = r-i+1; r = r+1; while (r < s.size() && s[l] == s[r]) { l++; r++; } l = i; r--; zArr[i] = r-l+1; } } if (zArr[i] + i == s.size()) res.push_back(zArr[i]); } /* for (int i = res.size()-1; i >= 0; i--) { cout << res[i] << " "; } */ vector<int> mult(n); mult[0] = 1; for (int i = 1; i < mult.size(); i++) mult[i] = (mult[i-1] * 26) % mod; vector<int> dp(n); for (int i = 0; i < s.size(); i++) { dp[i] = 0; } dp[s.size()-1] = 1; for (int i = s.size(); i < dp.size(); i++) { dp[i] = mult[i-s.size()+1]; for (int j = 0; j < res.size(); j++) { dp[i] = (dp[i] - dp[i-s.size()+res[j]]) % mod; } for (int j = 0; j <= i-s.size(); j++) dp[i] = (dp[i] - dp[j]*mult[i-s.size()-j]) % mod; dp[i] = (dp[i] + mod) % mod; //cout << i << ": " << dp[i] << endl; } int result = 0; int multiple = 1; for (int i = n-1; i >= 0; i--) { result += dp[i] * multiple; multiple *= 26; multiple %= mod; result %= mod; } cout << result; } signed main() { //cin.tie(0); //ios_base::sync_with_stdio(false); int t = 1; //ifstream f("testcase.txt"); //cin.rdbuf(f.rdbuf()); //cin >> t; while (t--) { solve(); } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
100 YWANYWAZYWANYWA |
correct output |
---|
134837038 |
user output |
---|
134837038 |
Test 2
Verdict: ACCEPTED
input |
---|
100 EDMXEDVNEDMXED |
correct output |
---|
642715950 |
user output |
---|
642715950 |
Test 3
Verdict: ACCEPTED
input |
---|
100 SDARSDAWVSDARSDA |
correct output |
---|
748728234 |
user output |
---|
748728234 |
Test 4
Verdict: ACCEPTED
input |
---|
100 HBDHBSHBDHB |
correct output |
---|
594110560 |
user output |
---|
594110560 |
Test 5
Verdict: ACCEPTED
input |
---|
100 CUNXUYGNGNEROXVLASQB |
correct output |
---|
675706202 |
user output |
---|
675706202 |
Test 6
Verdict: ACCEPTED
input |
---|
1000 LZAOLRKGLZAOLXLZAOLRKGLZAOLTLZ... |
correct output |
---|
318756627 |
user output |
---|
318756627 |
Test 7
Verdict: ACCEPTED
input |
---|
1000 SUASJSUASSGDSUASJSUASGKSUASJSU... |
correct output |
---|
367950233 |
user output |
---|
367950233 |
Test 8
Verdict: ACCEPTED
input |
---|
1000 NHYGNHEWNHYGNHFSNHYGNHEWNHYGNH... |
correct output |
---|
849646061 |
user output |
---|
849646061 |
Test 9
Verdict: ACCEPTED
input |
---|
1000 ZOCUZOCGRFZOCUZOCOQZOCUZOCGRFZ... |
correct output |
---|
32142571 |
user output |
---|
32142571 |
Test 10
Verdict: ACCEPTED
input |
---|
1000 LJZMKDTECKBXBTQQUMLGADBDNGWGPY... |
correct output |
---|
26128120 |
user output |
---|
26128120 |
Test 11
Verdict: ACCEPTED
input |
---|
1 A |
correct output |
---|
1 |
user output |
---|
1 |
Test 12
Verdict: ACCEPTED
input |
---|
100 AVXETIDRHKPAKRBEAAVHLOPFACULSE... |
correct output |
---|
228794815 |
user output |
---|
228794815 |
Test 13
Verdict: ACCEPTED
input |
---|
3 ABC |
correct output |
---|
1 |
user output |
---|
1 |
Test 14
Verdict: ACCEPTED
input |
---|
745 RRQOVUJRQBIMIQK |
correct output |
---|
504765084 |
user output |
---|
504765084 |
Test 15
Verdict: ACCEPTED
input |
---|
666 ABCABCDABCABCX |
correct output |
---|
920654188 |
user output |
---|
920654188 |
Test 16
Verdict: ACCEPTED
input |
---|
6 AA |
correct output |
---|
2212651 |
user output |
---|
2212651 |
Test 17
Verdict: ACCEPTED
input |
---|
1 B |
correct output |
---|
1 |
user output |
---|
1 |
Test 18
Verdict: ACCEPTED
input |
---|
1000 OMAKARAAA |
correct output |
---|
408042378 |
user output |
---|
408042378 |