QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#89829#5065. Beautiful StringpoiTL 2ms3748kbC++2.3kb2023-03-21 15:58:292023-03-21 15:58:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-21 15:58:32]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3748kb
  • [2023-03-21 15:58:29]
  • 提交

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

result: