「NOIP2020」字串匹配 (string)
題解
我堅持使用考場上想出來的 O ( 26 n + n ln ? n ) O(26n+n\ln n) O(26n+nlnn) 的做法，并成功地切掉了這道題，
無他，但卡常耳，
我的做法是列舉 ( A B ) i (AB)^i (AB)i 的右邊界 k k k，設 l i l_i li? 表示子串 S 1.. i S_{1..i} S1..i? 的最短回圈，那么 A B AB AB 必定是由若干個 l k l_k lk? 首尾相接組合而成的，我們可以直接列舉每一種可能的 A B AB AB ，時間復雜度 O ( n ln ? n ) O(n\ln n) O(nlnn) ，
那么每一個 A B AB AB 內有多少個合法的 A A A 使得 F ( A ) ≤ F ( C ) F(A)\le F(C) F(A)≤F(C) 呢？設 f i , j f_{i,j} fi,j? 表示 S 1.. i S_{1..i} S1..i? 中，滿足 F ( S 1.. x ) ≤ j , x < i F(S_{1..x})\le j,x<i F(S1..x?)≤j,x<i 的 x x x 的個數（也就是若以 S 1.. i S_{1..i} S1..i? 為 A B AB AB ，其中合法的 A A A 的個數），
求 f i , j f_{i,j} fi,j? 的時間復雜度是 O ( 26 n ) O(26n) O(26n) 的，用它來計算答案則是 O ( 1 ) O(1) O(1) 的，
但是這樣子做要列舉一個數的所有因子，由于這個上限很大，只能用 vector 了，這使得常數很大只有
84
84
84 分，
卡常及優化
下面開始卡常+優化，
優化1
用 reserve 函式可以提高 vector 的效率，這個我在考場上就用了，但是還是只有
84
84
84 分，
優化2
對于每個數
i
i
i ，只儲存小于等于
i
\sqrt{i}
i
? 的因子，然后把因子數大于等于
38
38
38 的扔進 vector ，小于等于
38
38
38 的用陣列直接存，再加上一系列奇奇怪怪的運算優化，終于在本地跑進了1s，然而交到OJ上還是 TLE84 了，
代碼：
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize("Ofast")
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
#define fo(i,l,r) for(i=l;i<=r;++i)
#define N 1048585
const int P=998244353;
int a[N],len[N],num[N],lsl[N],id[N],fa[N][39],siz[N],b[N];
char s[5][N],buf[100005],*l=buf,*r=buf;
ll f[N][26],pow1[N];
vector<int>fac[10005];
bool cnt[26];
inline char gc()
{return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;}
inline void read1(int &k)
{
char ch;while(ch=gc(),ch<'0'||ch>'9');k=ch-48;
while(ch=gc(),ch>='0'&&ch<='9') k=k*10+ch-48;
}
inline int read2(int k)
{
char ch;int len=0;
while(ch=gc(),ch<'a'||ch>'z');s[k][++len]=ch;
while(ch=gc(),ch>='a'&&ch<='z') s[k][++len]=ch;
return len;
}
inline int minus(int x,ll y){x-=y;return x<0?x+P:x;}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int T,t,n,tot,now1,lim,maxn=0,maxm,all=0;
ll ans;register int i,j,k;
read1(t),--t;
fo(i,0,t)
{
lsl[i]=read2(i);
if(lsl[i]>maxn) maxn=lsl[i];
}
maxm=sqrt(maxn),pow1[0]=1;
fo(i,1,maxn) pow1[i]=26*pow1[i-1]%P;
fo(i,1,maxm)
for(int j=i*i;j<=maxn;j+=i) ++num[j];
fo(i,1,maxn) if(num[i]>38)
id[i]=++all,fac[all].reserve(num[i]);
fo(i,1,maxm)
for(int j=i*i;j<=maxn;j+=i)
id[j]?fac[id[j]].push_back(i),0:fa[j][++siz[j]]=i;
fo(T,0,t)
{
ans=0,n=lsl[T],tot=0,
memset(b,0,sizeof b),
memset(len,0,sizeof len),
memset(cnt,0,sizeof cnt);
fo(i,1,n) a[i]=(26LL*a[i-1]+s[T][i]-97)%P;
fo(i,1,n)
{
(cnt[s[T][i]-97]^=1)?++tot:--tot;
fo(j,0,25) f[i][j]=f[i-1][j];
++f[i][tot],b[i]=tot;
}
fo(i,1,n) fo(j,1,25) f[i][j]+=f[i][j-1];
fo(i,1,n) if(!len[i])
{
len[i]=i;
for(j=i<<1;j<=n;j+=i)
{
if(minus(a[j],a[j-i]*pow1[i]%P)^a[i]) break;
len[j]=i;
}
}
memset(cnt,0,sizeof cnt),
cnt[s[T][n]-97]=1,tot=1;
for(i=n-1;i;--i)
{
lim=i/len[i];
if(id[lim]) for(j=0;j<fac[id[lim]].size();++j)
{
k=fac[id[lim]][j],
ans+=(len[i]<<1<=i?k/2*f[len[i]<<1][tot]:0)+(k&1?f[len[i]][tot]:0)-(b[k*len[i]]<=tot);
if(lim==k*k) break;
k=lim/k,
ans+=(len[i]<<1<=i?k/2*f[len[i]<<1][tot]:0)+(k&1?f[len[i]][tot]:0)-(b[k*len[i]]<=tot);
}
else for(j=1;j<=siz[lim];++j)
{
k=fa[lim][j],
ans+=(len[i]<<1<=i?k/2*f[len[i]<<1][tot]:0)+(k&1?f[len[i]][tot]:0)-(b[k*len[i]]<=tot);
if(lim==k*k) break;
k=lim/k,
ans+=(len[i]<<1<=i?k/2*f[len[i]<<1][tot]:0)+(k&1?f[len[i]][tot]:0)-(b[k*len[i]]<=tot);
}
(cnt[s[T][i]-97]^=1)?++tot:--tot;
}
printf("%lld\n",ans);
}
return 0;
}
優化3
優化2 說明先列舉倍數再列舉約數是 不可行 的，
那我們就反過來吧！
大改后，在OJ上測出了 96 96 96 分的好成績，
但是我還要再優化，
優化4
聽說自然溢位是可行的，只要把哈希改為 27 27 27 進制數就行，遂改之，
然后換了那個更長的火車頭，但是極限資料還是1000多ms，
接著嘗試了很多方法，都不可行，
回圈展開是不可行的，因為要進行很多次 i+1 ，i+2 之類的運算，效率沒有太大變化，甚至會更慢，
卡了一個多小時后，突然發現我有兩個 0 or ? 1 → 25 0 \operatorname{or} 1\to 25 0or1→25 的回圈，第一個是
fo(j,0,25) f[i][j]=f[i-1][j];
第二個是
fo(j,1,25) f[i][j]+=f[i][j-1];
我先完全展開了第二個回圈，發現快了 120 ms ? 120\operatorname{ms} 120ms ！！！
再展開第一個回圈，發現又回到了 1000 ms ? 1000\operatorname{ms} 1000ms 了？？？
那就只展開第二個回圈吧！
后來發現在其它OJ上不用火車頭也能過，
代碼
#pragma GCC optimize(3)
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstring>
#include<cstdio>
using namespace std;
typedef unsigned long long llu;
typedef long long ll;
#define N 1048577
const int maxn=1048576;
ll f[N][26];
int b[N],F[N],len[N],s[N];
char cnt[26],buf[100005],*l=buf,*r=buf;
llu pow26[N],a[N];
inline char gc()
{return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;}
inline void read1(int &k)
{
int ch;while(ch=gc(),ch<48||ch>57);k=ch-48;
while(ch=gc(),ch>=48&&ch<=57) k=k*10+ch-48;
}
inline int read2()
{
int ch;int len=0;
while(ch=gc(),ch<97||ch>122);s[++len]=ch-97;
while(ch=gc(),ch>=97&&ch<=122) s[++len]=ch-97;
return len;
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
llu ans;register int i,j,k;
int T,t,n,tot;
read1(t),pow26[0]=1;
for(i=1;i<=maxn;++i) pow26[i]=27llu*pow26[i-1];
for(T=0;T<t;++T)
{
ans=0,tot=0,n=read2(),
memset(len,0,sizeof len),
memset(cnt,0,sizeof cnt);
for(i=1;i<=n;++i) a[i]=27llu*a[i-1]+s[i];
for(i=1;i<=n;++i)
{
b[i]=(cnt[s[i]]^=1)?++tot:--tot;
for(j=0;j<=25;++j) f[i][j]=f[i-1][j];
++f[i][tot];
}
for(i=1;i<=n;++i)
{
f[i][1]+=f[i][0],
f[i][2]+=f[i][1],
f[i][3]+=f[i][2],
f[i][4]+=f[i][3],
f[i][5]+=f[i][4],
f[i][6]+=f[i][5],
f[i][7]+=f[i][6],
f[i][8]+=f[i][7],
f[i][9]+=f[i][8],
f[i][10]+=f[i][9],
f[i][11]+=f[i][10],
f[i][12]+=f[i][11],
f[i][13]+=f[i][12],
f[i][14]+=f[i][13],
f[i][15]+=f[i][14],
f[i][16]+=f[i][15],
f[i][17]+=f[i][16],
f[i][18]+=f[i][17],
f[i][19]+=f[i][18],
f[i][20]+=f[i][19],
f[i][21]+=f[i][20],
f[i][22]+=f[i][21],
f[i][23]+=f[i][22],
f[i][24]+=f[i][23],
f[i][25]+=f[i][24];
}
for(i=1;i<=n;++i) if(!len[i])
{
len[i]=i;
for(j=i<<1;j<=n&&a[j]-a[j-i]*pow26[i]==a[i];j+=i)
len[j]=i;
}
memset(cnt,0,sizeof cnt),tot=0;
for(i=n;i;--i) F[i]=(cnt[s[i]]^=1)?++tot:--tot;
for(i=1;i<=n;++i)
for(j=i;j<n&&len[j]==i;j+=i)
for(k=j;k<n&&len[k]==i;k+=j)
ans+=f[j][F[k+1]]-(b[j]<=F[k+1]);
printf("%llu\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237976.html
標籤：其他