M_sea

洛谷4548 [CTSC2006]歌唱王国
Luogu分析听了 laofu 的讲课并看了 ymd 的论文后做了这题。以下统一规定 $n$ 为字符集大小,$m$...
扫描右侧二维码阅读全文
25
2019/07

洛谷4548 [CTSC2006]歌唱王国

Luogu

分析

听了 laofu 的讲课并看了 ymd 的论文后做了这题。

以下统一规定 $n$ 为字符集大小,$m$ 为名字长度。

设 $f_i$ 表示长度为 $i$ 时结束的概率,$g_i$ 表示长度为 $i$ 时没有结束的概率。

设 $f_i$ 的概率生成函数为 $F(x)$ ,$g_i$ 的概率生成函数为 $G(x)$ 。

根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。

分析一下可以列出这样一个式子

$$ \displaystyle xG(x)+1=F(x)+G(x)\qquad\cdots\ (1) $$

这个式子的意义是加一个字符后可能结束也可能没有结束。感觉是废话,但是真的可以列一个式子

再分析一下可以列出这样一个式子

$$ \displaystyle G(x)\cdot\left(\frac{1}{n}x\right)^m=\sum_{i=1}^ma_i\cdot F(x)\cdot\left(\frac{1}{n}x\right)^{m-i}\qquad\cdots\ (2) $$

这里的 $a_i$ 表示 $[1,i]$ 是否是名字的一个 border 。

这个式子的意义是在一个未结束的序列后加上名字一定会结束,但是有可能在没有到 $m$ 个字符时就结束了,此时添加的序列是名字的一个 border 。

把 $(1)$ 求导可以得到

$$ \displaystyle \begin{aligned} xG'(x)+G(x)&=F'(x)+G'(x)\\ F'(x)&=(x-1)G'(x)+G(x)\qquad\cdots\ (3) \end{aligned} $$

把 $x=1$ 代入 $(3)$ 可以得到

$$ \displaystyle F'(x)=G(x)\qquad\cdots\ (4) $$

把 $x=1$ 代入 $(2)$ 可以得到

$$ \displaystyle \begin{aligned} G(1)\cdot\left(\frac{1}{n}\right)^m&=\sum_{i=1}^ma_i\cdot F(1)\cdot\left(\frac{1}{n}\right)^{m-i}\\ G(1)&=\sum_{i=1}^ma_i\cdot F(1)\cdot n^i\\ G(1)&=\sum_{i=1}^ma_i\cdot n^i\qquad\cdots\ (5) \end{aligned} $$

联立 $(4)(5)$ 可以得到

$$ \displaystyle F'(1)=\sum_{i=1}^ma_i\cdot n^i $$

用 KMP / hash 求出 $a_i$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=10000;

int n,t,m;
int s[N],pw[N],nxt[N];

inline void solve() {
    m=read();
    for (re int i=pw[0]=1;i<=m;++i) pw[i]=pw[i-1]*n%mod;
    for (re int i=1;i<=m;++i) s[i]=read();
    for (re int i=2,j=0;i<=m;++i) {
        while (j&&s[j+1]!=s[i]) j=nxt[j];
        if (s[j+1]==s[i]) ++j;
        nxt[i]=j;
    }
    int ans=0;
    for (re int i=m;i;i=nxt[i]) ans=(ans+pw[i])%mod;
    printf("%04d\n",ans);
}

int main() {
    n=read(),t=read();
    for (re int i=1;i<=t;++i) solve();
    return 0;
}
最后修改:2019 年 08 月 27 日 09 : 15 AM

8 条评论

  1. heyujun

    你的$G(x)$不应该是普通型生成函数吗?

    1. M_sea
      @heyujun

      你可以这么理解吧...只是把它叫做概率生成函数而已 ...

      1. memset0
        @M_sea

        应该是 f_i 的普通生成函数,长度为 i 时结束的概率生成函数吧(瞎说的

        1. M_sea
          @memset0

          改了qaq

          1. memset0
            @M_sea

            我是错的,您原来那份是对的。麻烦您改回来吧...抱歉!

            1. memset0
              @memset0

              等下好像两种说法都有,那我还是坚持下我原来的观点吧orz。

  2. memset0

    羡慕能听 laofu 讲课的 ...

    1. M_sea
      @memset0

      QAQ

发表评论