QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89829 | #5065. Beautiful String | poi | TL | 2ms | 3748kb | C++ | 2.3kb | 2023-03-21 15:58:29 | 2023-03-21 15:58:32 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 5e3 + 10;
const int P = 418254373 , Q = 1e9 + 7;
const int bp = 131 , bq = 137;
int n , m;
char ch[MAXN];
#define qm( a , p ) ( (a) < p ? (a) : (a) - p )
pii operator + ( const pii& a , const pii& b ) {
return mp( qm( a.fi + b.fi , P ) , qm( a.se + b.se , Q ) );
}
pii operator - ( const pii& a , const pii& b ) {
return mp( qm( a.fi + P - b.fi , P ) , qm( a.se + Q - b.se , Q ) );
}
pii operator * ( const pii& a , const pii& b ) {
return mp( a.fi * 1ll * b.fi % P , a.se * 1ll * b.se % Q );
}
int Pow( int x , int a , int p ) {
int ret = 1;
while( a ) {
if( a & 1 ) ret = ret * 1ll * x % p;
x = x * 1ll * x % p , a >>= 1;
}
return ret;
}
pii hsh[MAXN] , iv[MAXN] , bs[MAXN];
pii que( int l , int r ) {
return ( hsh[r] - hsh[l - 1] ) * iv[l - 1];
}
map<pii,int> M;
int re[MAXN][MAXN];
void solve() {
M.clear();
scanf("%s",ch + 1);
n = strlen( ch + 1 );
rep( i , 1 , n ) hsh[i] = hsh[i - 1] + bs[i] * mp( ch[i] - '0' + 1 , ch[i] - '0' + 1 );
per( p , n , 1 ) {
per( i , p - 1 , 1 ) if( M.count( que( i , p - 1 ) ) ) {
re[i][p - i] = M[que( i , p - 1 )];
}
rep( i , p , n )
++ M[que( p , i )];
}
rep( i , 1 , n ) per( j , n , 1 ) re[i][j] += re[i][j + 1];
ll res = 0;
rep( i , 1 , n ) rep( j , i , n ) if( que( i , j ) == que( j + 1 , j + 1 + ( j - i ) ) ) {
res += re[j + 1][j - i + 2];
}
cout << res << endl;
rep( i , 1 , n ) rep( j , 1 , n ) re[i][j] = 0;
}
signed main() {
bs[0] = mp( 1 , 1 ) , bs[1] = mp( bp , bq );
rep( i , 2 , MAXN - 2 ) bs[i] = bs[i - 1] * bs[1];
iv[0] = mp( 1 , 1 ) , iv[1] = mp( Pow( bp , P - 2 , P ) , Pow( bq , Q - 2 , Q ) );
rep( i , 2 , MAXN - 2 ) iv[i] = iv[i - 1] * iv[1];
// freopen("in","r",stdin);
// freopen("out","w",stdout);
int T;cin >> T;while( T-- ) solve();
// solve();
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3748kb
input:
2 114514 0000000
output:
1 3
result:
ok 2 number(s): "1 3"
Test #2:
score: -100
Time Limit Exceeded
input:
11 79380 2483905227 37902399703986576270 39991723655814713848046032694137883815354365954917 5541883522667841718787744915558298207485830622522715211018760095628594390563630840464643840093757297 56530485554219245862513973750218715585679416120445975390556326891488719311495909340757506478400624741858999...
output:
0 0 0 2 4 20 119 113 1086