当前位置:网站首页>F - birthday cake (Shandong race)
F - birthday cake (Shandong race)
2022-07-06 16:03:00 【It's Xiao Zhang, ZSY】
Moca’s birthday is coming up, and her friend Ran is going to the Yamabuki bakery to order a birthday cake for her.
Yamabuki bakery provides nn kinds of cake. Since Ran knows that Moca is the Yamabuki Bakery’s 11-st fan and can eat a lot of food, she intends to order two cakes and put them together into a big cake. The cake made by Yamabuki bakery can be formed by a string consisting of lowercase Latin letters, which describes the toppings on the cake, such as strawberries and chocolate. Putting two cakes together is the concatenation of two corresponding strings. For example, the result of putting cake ab and cake cabc together is a big cake abcabc.
To make it easier to share the cake, Ran will choose two cakes and put them together into a big cake which can be divided in half into two identical pieces. For example, cake abcabc will be divided in half into two cakes abc, but cake abbc will be divided in half into two different cakes ab and bc. Notice that Ran can not reverse the cake, which means that cake abba will be divided into two different cakes ab and ba.
Can you help Ran figure out how many different pairs of cakes meet the above condition?
Input
The first line contains one integer n(1≤n≤4e5)– the number of cakes.
The next n lines describe all the cakes, where the ii-th line contains one string si(1≤∣s ≤4e5)consisting of lowercase Latin letters.
It is guaranteed that the sum of lengths of cakes does not exceed 4e5
Output
Print one integer – the number of pairs of cakes meet the above condition.
Inputcopy
3
ab
ab
cabc
Outputcopy
3
My idea is to look at the prefix and suffix of a string , If these two prefixes are equal , Just check whether the remaining part of the string after removing the pre suffix has ever appeared , Then count the number of answers ps We arrange all strings according to their length from small to large , Be sure to row , Otherwise aaaa,aa This data can be stuck out .
// I still don't know why I wrote the wrong code for the first time
// Looking at the official explanation, I think the idea is very right ,,, Purr, purr, purr
// The official is double hash ,<< Last night because of this topic acwing Learned hash table >>
// The questioner got stuck with natural overflow and some common modulus single hashes , So use double hash ,ps: If yes, it is a hash problem , When you see that the pass rate is outrageous , Consider the possibility of double hashing .
//blog.csdn.net/weixin_45672411/article/details/116720502
// If you can't hash , Suggest to see it acwing841, Coming back to this question, it's very simple ;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PII;
map<PII,int>ma;
int const N=4e5+10;
int P=131;// perhaps p=13331;
ll p1[N],p2[N],h1[N],h2[N];
ll const mod1=1e9+7,mod2=1e9+9;
int n;
char s[N];
string ss[N];
bool cmp(string s1,string s2)
{
return s1.size()<s2.size();
}
// Interval and formula h[l,r]=h[r]−h[l−1]×P[r−l+1];
ll check1(int l,int r)
{
if(l>r)
return 0;
return (h1[r]-h1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;
}
ll check2(int l,int r)
{
if(l>r)
return 0;
return (h2[r]-h2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;
}
int main()
{
// Find greater than 1e9 The smallest prime number ,1e9+7,1e9+9;
/* int flag=2; for(ll i=1000000000; ;i++) { int kk=0; for(ll j=2;j<=i/j;j++) { if(i%j==0) { kk=1; break; } } if(kk==0) { cout<<i<<endl; flag--; } if(!flag) break; }*/
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
p1[0]=1,p2[0]=1;
for(int i=1; i<N; i++)
{
p1[i]=p1[i-1]*P%mod1; // Horner scheme ,131 Turn into the system 10 Base number
p2[i]=p2[i-1]*P%mod2;
}
cin>>n;
for(int i=1; i<=n; i++)
cin>>ss[i];
sort(ss+1,ss+1+n,cmp);
ll ans=0;
for(int i=1; i<=n; i++)
{
int len=ss[i].size();
for(int j=1; j<=len; j++)
s[j]=ss[i][j-1];
for(int j=1; j<=len; j++)
{
// Prefixes and formulas h[i+1]=h[i]*P+s[i];
h1[j]=(h1[j-1]*P%mod1+s[j])%mod1;
h2[j]=(h2[j-1]*P%mod2+s[j])%mod2;
}
for(int j=1;j<=len-j+1;j++)
{
int r=len-j+1;
if(check1(1,j)==check1(r,len)&&check2(1,j)==check2(r,len))
{
ans+=ma[{
check1(j+1,r-1),check2(j+1,r-1)}];
}
}
ans+=ma[{
check1(1,len),check2(1,len)}];
ma[{
check1(1,len),check2(1,len)}]++;
}
cout<<ans<<endl;
return 0;
}
边栏推荐
- STM32 how to use stlink download program: light LED running light (Library version)
- MySQL grants the user the operation permission of the specified content
- Cost accounting [23]
- Determine the Photo Position
- C语言学习笔记
- 信息安全-安全编排自动化与响应 (SOAR) 技术解析
- Nodejs+vue网上鲜花店销售信息系统express+mysql
- 渗透测试 ( 4 ) --- Meterpreter 命令详解
- 【练习-6】(PTA)分而治之
- Optimization method of path problem before dynamic planning
猜你喜欢
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
Web based photo digital printing website
X-forwarded-for details, how to get the client IP
Penetration test (8) -- official document of burp Suite Pro
Pyside6 signal, slot
frida hook so层、protobuf 数据解析
Ball Dropping
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
Nodejs+vue online fresh flower shop sales information system express+mysql
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
随机推荐
Penetration test (1) -- necessary tools, navigation
Market trend report, technical innovation and market forecast of geosynthetic clay liner in China
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
Common configuration files of SSM framework
Alice and Bob (2021牛客暑期多校训练营1)
Opencv learning log 18 Canny operator
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
Cost accounting [24]
Information security - Analysis of security orchestration automation and response (soar) technology
Determine the Photo Position
China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
D - Function(HDU - 6546)女生赛
CS zero foundation introductory learning record
If you want to apply for a programmer, your resume should be written like this [essence summary]
0-1背包問題(一)
【练习-5】(Uva 839)Not so Mobile(天平)
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
Ball Dropping
Opencv learning log 33 Gaussian mean filtering