[BZOJ] 1152. [CTSC2006] 노래의 왕국 싱글랜드. - 등 확률이 랜덤으로 일치하는 결론에 대한 추론

전송문:bzoj1152 아래에 초양심 유도!
이 문제는 이전에 결론만 알고 코드가 이렇게 생겼다.

#include
using namespace std;
const int N=1e5+50;
const int mod=1e4;
int n,t,len,tp;
int nxt[N],a[N],dp[N];

int main(){
    int i,j,kmp;
    scanf("%d%d",&n,&t);
    while(t--){
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&len,&a[1]);
        dp[1]=n;tp=n;kmp=0;
        for(i=2;i<=len;++i){
            scanf("%d",&a[i]);
            for(;kmp && a[kmp+1]!=a[i];kmp=nxt[kmp]);
            kmp+= a[kmp+1]==a[i]?1:0;
            tp=1ll*tp*n%mod;
            dp[i]=(dp[(nxt[i]=kmp)]+tp)%mod;
        }
        printf("%04d
",dp[len]);
    }
}

그리고 항상 의식적으로mod=1e5m o d=1e5라고 쓰여서 매번 제출할 때마다 먼저 WA를 한 번...이제 VFK V F K 신번 블로그가 드디어 유도된다!그리고 다음 코드로 로곡rk1, bzojrk4에 카드를 넣으세요.
코드는 다음과 같다.

#include
using namespace std;
const int N=1e5+100,mod=1e4;

int n,m,que,nxt[N],pw[N],ans;
int a[N];

inline int ad(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}

inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}

char c;
inline void rd(int &x)
{
    c=gc();x=0;
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);c=gc()) x=x*10+(c^48);
}

int main(){
    register int i;int kmp,lim=0;pw[0]=1;
    rd(n);rd(que);
    for(;que;--que){
        rd(m);
        if(m>lim) {
          for(i=lim+1;i<=m;++i) pw[i]=1ll*pw[i-1]*n%mod;
          lim=m;
        } 
        for(i=1;i<=m;++i) rd(a[i]);
        nxt[1]=kmp=0;
        for(i=2;i<=m;++i){
            for(;a[kmp+1]!=a[i] && kmp;kmp=nxt[kmp]);
            nxt[i]=(kmp+= (a[kmp+1]==a[i]));
        }
        for(ans=0,i=m;i;i=nxt[i]) ans=ad(ans,pw[i]);
        printf("%04d
",ans);
    }
}

유도

먼저 추론 방법은 모두 VFK V F K 신번을 본떠서 기록한 것일 뿐 아니라 LaTeX L a T e X 렌더링의 공식도 눈에 많이 띈다.
기호 설명:

s는 목표 숫자열을 대표하고ansa ns는 평균 노래 시간을 대표한다.

임의의 소문자(예를 들어 aa)로 특정한 숫자열을 나타낼 수도 있고 단일 숫자로 구성된 숫자열을 나타낼 수도 있다.AA와 같은 모든 대문자로 조건을 충족하는 숫자열의 집합을 나타냅니다.

|a|||a | 숫자열 a의 길이를 나타냅니다.

abab는 숫자열 bb가 숫자열 aa에 연결된 후 구성된 숫자열을 나타낸다. 즉, 숫자열 a, ba, b가 연결된 문자열이다.

A∪ B∪ B는 숫자열 집합 A와 숫자열 집합 B의 합집합을 나타낸다.

A B A B는 숫자열 집합 AA와 숫자열 집합 BB의 교집합을 나타낸다.

ϕ ϕ 빈 문자열을 표시합니다. (빈 집합의 기호 코드를 찾지 못하면 오라 함수로 대체합니다.)

주어진 집합:

숫자열 집합 QQ, Q={a|a 즉 s의 접두사이자 s의 접두사, a≠ϕ} Q = a | a는 s의 접미사이자 s의 접미사이며 a≠ϕ }

숫자열 집합 P P, P={a|a는 s의 접미사, a≠ϕ,a≠s, s는 a라는 접미사를 삭제하고 얻은 접두사 문자열 b∈Q} P = {a | a는 s의 접미사이고 a≠ϕ , a≠s,s는 a라는 접두사에서 얻은 접두사 문자열 b∈Q}

을 삭제합니다

숫자열 집합 Y Y, Y={a|s는 a에 한 번만 나타나고 s는 a의 접미사} Y = {a|s는 a에 한 번만 나타나며 s는 a의 접미사}

숫자 문자열 집합 N, N={a|s는 a의 문자열이 아니다. 즉, a에 s}가 나타나지 않는다. N = {a|s는 a의 문자열이 아니다. 즉, a에 s}가 나타나지 않는다.

ans=∑a∈Y|a|(1n)|a|a n s=∑a∈Y|a | (1n)| a |
그래서 f(A)=∑a∈A|a|(1n)|a|f(A)=∑a∈A|a|(1n)|a|a|간식자구f(Y)f(Y)를 설정할 수 있다고 생각했다.그러나 | a | a | a | f (A) f (A) 에서 두 번이나 나타나 쉽게 간소화할 수 없었다.
이에 g(A,z) = ∑a∈A(zn)|a|g(A,z)= ∑a∈A(zn)|a|, g(A,z)g(A,z)에서zz에 대해 편도된 g′(A,z) = ∑a∈A|a|(1n)|a|a||||-31g′(A,z)=∑a∈A|a|a|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
그러면 ans=f(Y)=g′(Y,1) a n s=f(Y)=g′(Y,1).먼저 g(A,z) = ∑a∈A(zn)|a|g(A,z)= ∑a∈A(zn)|a|를 구하고 그에 대해z의 편도를 구할 수 있다.
현재의 임무는 Y와 Y에 관한 등식을 찾아서 g(Y, 1)g(Y, 1)의 PP에만 관한 간략한 형식을 구하는 것이다.그래서 P, Y, N P, Y, N 사이의 관계를 살펴보자.
ϕ+∑a∈N∑ni=1ai=Y+N ϕ + ∑ a ∈ N ∑ i = 1 n a i = Y + N
∑a∈Nas=Y+∑a∈Y∑p∈Pap ∑ a ∈ N a s = Y + ∑ a ∈ Y ∑ p ∈ P a p
그런 다음 g(A,z) g(A,z)의 계산이 나열됩니다.

A B=ϕ A ∩ B = ϕ , g(A∪B,z)=g(A,z)+g(B,z) g ( A ∪ B , z ) = g ( A , z ) + g ( B , z )

g(∑a∈Aab,z)=(zn)|b|g(A,z) g ( ∑ a ∈ A a b , z ) = ( z n ) | b | g ( A , z )

g(∑a∈A∑b∈Bab,z)=g(A,z)g(B,z) g ( ∑ a ∈ A ∑ b ∈ B a b , z ) = g ( A , z ) g ( B , z )

위의 두 등식을 g(A,z) g(A,z) 형식으로 변환합니다.
g(ϕ,z)+(∑ni=1zn)g(N,z)=g(Y,z)+g(N,z) g ( ϕ , z ) + ( ∑ i = 1 n z n ) g ( N , z ) = g ( Y , z ) + g ( N , z )
(zn)|s|g(N,z)=g(Y,z)+g(Y,z)g(P,z) ( z n ) | s | g ( N , z ) = g ( Y , z ) + g ( Y , z ) g ( P , z )
살짝:
1+zg(N,z)=g(Y,z)+g(N,z) 1 + z g ( N , z ) = g ( Y , z ) + g ( N , z )
(zn)|s|g(N,z)=(1+g(P,z))g(Y,z) ( z n ) | s | g ( N , z ) = ( 1 + g ( P , z ) ) g ( Y , z )
방정식을 크게 풀고 g(P,z) g(P,z)로 g(Y,z) g(Y,z)를 나타냅니다.
g(Y,z)=(zn)|s|g(P,z)−zg(P,z)−z+1+(zn)|s| g ( Y , z ) = ( z n ) | s | g ( P , z ) − z g ( P , z ) − z + 1 + ( z n ) | s |
식자항이 비교적 많기 때문에 설정분자에 따라 h(z)h(z), 분모는 q(z)q(z)로 나뉘어zz에 대한 편도화:
h(z)=(zn)|s|,h′(z)=|s|(1n)|s|z|s|−1 h ( z ) = ( z n ) | s | , h ′ ( z ) = | s | ( 1 n ) | s | z | s | − 1
q(z)=∑a∈P(zn)|a|−∑a∈Pz|a|+1(1n)|a|−z+1+(zn)|s| q ( z ) = ∑ a ∈ P ( z n ) | a | − ∑ a ∈ P z | a | + 1 ( 1 n ) | a | − z + 1 + ( z n ) | s |
q′(z)=∑a∈P|a|(1n)|a|z|a|−1−∑a∈P(|a|+1)(1n)|a|z|a|−1+0+|s|(1n)sz|s|−1 q ′ ( z ) = ∑ a ∈ P | a | ( 1 n ) | a | z | a | − 1 − ∑ a ∈ P ( | a | + 1 ) ( 1 n ) | a | z | a | − 1 + 0 + | s | ( 1 n ) s z | s | − 1
z=1z=1,득:
h(1)=(1n)|s|,h′(1)=|s|(1n)|s| h ( 1 ) = ( 1 n ) | s | , h ′ ( 1 ) = | s | ( 1 n ) | s |
q(1)=(1n)|s|,q′(1)=|s|(1n)|s|−∑a∈P(1n)|a|−1 q ( 1 ) = ( 1 n ) | s | , q ′ ( 1 ) = | s | ( 1 n ) | s | − ∑ a ∈ P ( 1 n ) | a | − 1
리턴 원형:
g′(Y,1)=h′(1)q(1)−h(1)q′(1)q(1)q(1) g ′ ( Y , 1 ) = h ′ ( 1 ) q ( 1 ) − h ( 1 ) q ′ ( 1 ) q ( 1 ) q ( 1 )
계산을 대대적으로 끌어들였는데 기묘한 일이 일어났다. 이런 간단한 형식을 얻었다.
g′(Y,1)=∑a∈P(1n)|a|+1(1n)|s|=∑a∈Pn|s|−|a|+n|s| g ′ ( Y , 1 ) = ∑ a ∈ P ( 1 n ) | a | + 1 ( 1 n ) | s | = ∑ a ∈ P n | s | − | a | + n | s |
앞에서 정의한 숫자열 집합 PP의 성질은 |s|--|a||s|||||--a|실제적으로 QQ에서 ss 이외의 모든 숫자열의 길이를 매거하였고, ss도 다른 n|s|n |s | s|에 추가되었기 때문에 최종적으로:
ans=f(Y)=g′(Y,1)=∑a∈Qn|a| a n s = f ( Y ) = g ′ ( Y , 1 ) = ∑ a ∈ Q n | a |
숫자열 집합 QQ는 s에 대해 kmpkmp를 한 번 하면 구할 수 있기 때문에 n의 차멱을 미리 처리하는 것을 제외하고 복잡도는 O(n)O(n)이다.
그나저나 kmp k m p를 만드는 next n e x t 수조의 복잡도는 어떻게 증명합니까?이것은 자신의 뇌보신의 증명이다.
건립 과정 중 매번 문자를 추가하면 kmp k m p는 최대 한 자리를 뒤로 옮깁니다. 매칭에 실패할 때마다next n e x t체인을 뛰면 최소한 한 자리를 뒤로 옮깁니다. (초기 위치에 도착하지 않은 경우)총 xx회nextnext체인을 설정하고 문자열 길이가 nn이면 nxtn≤n-3 xne xtn≤n-3 x.0≤nextn코드는 식에 따라 대입하여 계산하면 된다.