PGF&&DGF 学习笔记

· · 算法·理论

PGF 学习笔记

性质与定义

基本全是口胡的，有错给我说。

全称概率型生成函数，基本形式如：F(x)=\sum\limits_{i\geq 0}P(X=i)x^i，有很多离奇的性质，所以被出成了各种奇怪题（首先你要保证概率是离散的）。

理由：不难发现 x=1 时，概率和为一。

实际上，离散好像不是硬性要求，但是不离散好像没什么意义。

理由：不难发现 F^{'}(x)=\sum\limits_{i\geq 1}P(X=i)i·x^{i-1}，得到 F^{'}(1)=\sum\limits_{i\geq 0}P(X=i)i=E(X)。

理由：说实话不知道有啥大用，但是可以推导之后的式子，E(x^{\underline k})=\sum\limits_{i\geq 0}P(X=i)i^{\underline k}，多求几次导就能证明了。

理由：E(X^2)=E(X^{\underline 2}+X^{\underline 1})=F^{''}(1)+F^{'}(1)，比较有用的式子了，早点学多好呢？

理由后面会补，貌似《具体数学》第八章上面有。

有多项式和期望基础，可以直接看题了。

做题

注：某些题后面可能会有带误导性的口胡，算是一些自己的理解，最好别信。

P4548

比较牛的套路题，有助于认识 Trick。

记 [x^k]F(x) 表示唱了 k 个数后恰好唱出名字的概率，[x^k]G(x) 是唱了 k 个数后还没有唱出名字的概率。

这种方法是我最开始没有想到的，因为我想一步到位直接设出状态，太贪心了。

有：F(x)+G(x)=xG(x)+1。

理由：先看 +1 是怎么来的，发现唱 0 个数是不可能唱出名字的，所以 [x^0]G(x)=1，但是因为位移导致常数项丢失，故此需要 +1。

然后展开来：f_n+g_n=g_{n-1}，显然是对的，因为前 n-1 次没有唱出名字，所以第 n 次要么唱出名字，要么唱不出来。

对于两边同时求导：F^{'}(x)+G^{'}(x)=G(x)+xG^{'}(x)。

将 1 代入：F^{'}(1)=G(1)，两边可以同时消去 G^{'}(1)。

而由之前的性质，我们知道 E(X)=F^{'}(1)，所以只需要算出 G(1) 就可以了。

但是 G(1) 仍不好算，但是我们可以发现 F(1) 是好算的，也就是 1，所以如果我们导出了 G(x) 和 F(x) 的关系，再代一个 x=1 进去就完事大吉了。

接下来的转换比较神秘了，重要的套路。

我们构造出强制满足条件的生成函数，也即构造一组必然结束的情况。

不难发现是 G(x)(\frac xn)^m，其中 m 表示字符串的长度，直观解释为强行在后面拼接一个名字，使其一定能唱出来。

发现这玩意有点问题，因为可能会提前结束，也即：还没拼接完 m 个字符就已经结束。

对于这种情况，我们考虑对 F(x) 进行处理来保证计算是正确的。

我们用 A_i 表示长度为 i 的前缀是否是原串的 Border，由此有式子：G(x)(\frac xn)^m=\sum\limits_{i=1}^mA_iF(x)(\frac xn)^{m-i}。

理由：发现提前结束当且仅当目前串的末尾是原串的 Border，所以枚举 Border 长度即可处理提前结束的情况。

使用之前的思路，代入 x=1，并在两边同时乘上 n^m，可得 G(1)=\sum\limits_{i=1}^m A_in^i，可以 O(m) 的时间内完成。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int mod=10000;
struct modint {
    int val;
    static int norm(const int& x) { return x < 0 ? x + mod : x; }
    modint() : val(0) {}
    modint(const int& m) : val(norm(m)) {}
    modint& operator+=(const modint& o) { return val = (1ll * val + o.val) % mod, *this; }
    modint& operator*=(const modint& o) { return val = static_cast<int>(1ll * val * o.val % mod), *this; }
    modint operator+(const modint& o) const { return modint(*this) += o; }
    modint operator*(const modint& o) const { return modint(*this) *= o; }
};

const int N=2e5+10;
int n,t,a[N],nex[N],m;modint ans;
inline modint expow(modint x,int y){modint res=1;for(;y;y>>=1){if(y&1)res*=x;x*=x;}return res;}

int main(){
    scanf("%d%d",&n,&t);
    while(t--){
        scanf("%d",&m);ans=0;
        for(int i=1;i<=m;++i) scanf("%d",&a[i]);
        for(int i=1;i<=m;++i) nex[i]=0;
        for(int i=1,j=0;i<m;++i){
            while(j&&a[j+1]!=a[i+1]) j=nex[j];
            nex[i+1]=(j+=a[j+1]==a[i+1]);
        }
        int now=m;
        while(now){ans+=expow(n,now);now=nex[now];}
        printf("%04d\n",ans.val);
    }
    return 0;
}

嗯注意 G(x) 不是 PGF 而是 PGF 的一个后缀和，g_{n-1}-g_{n}=f_n，别搞错了。

然后生成函数特定情况下是可以代值的，但是你要保证函数时收敛的，比如 H(x)=\sum\limits_{i\geq 0}x^i 就不能代值。

其它例题

ARC136F，P3706，这篇文章，还可以去看一下「2013 Multi-University Training Contest 5」Dice。

然后讲解的话，这篇和这篇可以专门去看一下，如果想更深入的了解可以去翻 zhihu，上面有很多深刻的文章，只是 OI 里面不一定 pratical。

然后 ZJOI 的开关也是有 PGF 做法的，感觉稍微有点吃数学能力。

DGF 学习笔记

PGF 习题咕咕了，为了防止省选之前的时间太颓写一下 DGF 学习笔记。

感觉几乎用不上啊，大部分时候是用来分析问题而不是提供一种强力的计算套路。

不过这篇文章 link 挺有趣的。

这篇和这篇写得也比较深刻！

总的来说是比较精巧的东西吧！

性质与定义

也基本是口胡。

全称是狄利克雷生成函数，形如 F(x)=\sum\limits_{i=1}^n\frac{f_i}{i^x}。长相很怪异，\{1\}_{i=1}^\infty 的 DGF 是 F(x)=\sum\limits_{i=1}^n \frac 1{i^x}=\zeta(x)，也就是著名的黎曼函数。

一般是用来处理积性函数，也即 \forall i\bot j,f_{ij}=f_i\times f_j 的一系列函数，不难发现一个积性函数取值构成的 DGF 可以被拆分成和质数处取值相关的乘积式（以下称质数集合为 P）：

\begin{aligned} F(x)&=\sum\limits_{i=1}^n \frac{f_i}{i^x}\\ &=\prod_{p\in P}(1+\frac{f_p}{p^x}+\frac{f_{p^2}}{p^{2x}}+\dots)\\ \end{aligned}

相当的优雅。

考虑将部分经典的积性函数转化成 DGF 形式来加深理解。

黎曼函数 \zeta

\begin{aligned} \zeta(x)&=\prod_{p\in P }(1+\frac{1}{p^x}+\frac{1}{p^{2x}}+\dots)\\ &=\prod_{p\in P}(\frac{1}{1-p^{-x}}) \end{aligned}

不难发现黎曼函数是 DGF 下的 1 函数。

莫比乌斯函数 \mu

\begin{aligned} M(x)&=\prod_{p\in P}(1-\frac{1}{p^x}) \end{aligned}

不难发现 M(x)\zeta(x)=1。

这里就要谈一下 DGF 卷积的直观意义了：

\begin{aligned} F(x)G(x)&=\sum_{i=1}^\infty\sum_{j=1}^\infty\frac{f_i}{(ij)^x}\\ &=\sum_{i=1}^{\infty}\frac{1}{i^x}\sum_{d|n}f_dg_{\frac nd}\\ &=\sum_{i=1}^\infty \frac{1}{i^x}(f*g)(n)\\ \end{aligned}

所以 M(x)\zeta(x)=1 等价于 \mu*1=\epsilon，这里就能看出 DGF 的强大之处了。

欧拉函数 \varphi

\begin{aligned} \Phi(x)&=\prod_{p\in P}(1+\frac{p-1}{p^x}+\frac{p(p-1)}{p^{2x}}+\dots)\\ &=\prod_{p\in P}(1+(p-1)p^{-1}(\frac{1}{p^{x-1}}+\frac{1}{p^{2(x-1)}}+\dots))\\ &=\prod_{p\in P}(p^{-1}+\frac{1-p^{-1}}{1-p^{1-x}})\\ &=\prod_{p\in P}(\frac{1-p^{-x}}{1-p^{1-x}}) \end{aligned}

如果你往上面看一眼，不难发现 \Phi(x)=\frac{\zeta(x-1)}{\zeta(x)}。

幂函数 I_k

\begin{aligned} I_k(x)&=\prod_{p\in P}(1+\frac{p^k}{p^x}+\frac{p^{2k}}{p^{2x}}+\dots)\\ &=\prod_{p\in P}\frac{1}{1-p^{k-x}}\\ &=\zeta(x-k) \end{aligned}

联系上面 \varphi 相关内容可以证得：\varphi*1=I。

其实可以知道这玩意的作用之一是使数论函数的性质更加具体，从而弥补你天生较弱的注意力。

有例题：

相关应用

简单的数学题

算了还是推一下前面的吧。

记 f(x)=\frac{x(x+1)}{2}

\begin{aligned} \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)&=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor \frac nd \rfloor}\sum_{j=1}^{\lfloor \frac nd \rfloor}[i\bot j]\\ &=\sum_{d=1}^nd^3\sum_{k=1}^{\lfloor \frac nd\rfloor}\mu(k)k^2f(\lfloor \frac{n}{kd}\rfloor)^2\\ &=\sum_{T=1}^nT^2\varphi(T)f(\lfloor\frac nT\rfloor)^2 \end{aligned}

考虑对 f(\lfloor\frac nT\rfloor)^2 部分施以数论分块，并使用杜教筛对 g(T)=T^2\varphi(T) 进行前缀和计算。

考虑套路地找到一个数论函数 h(x)，使得 (g*h)(x) 和 h(x) 前缀和都比较好算，这个时候你可以选择使用超人的注意力什么的，我们考虑 DGF 对之进行推导。

\begin{aligned} G(x)&=\prod_{i=1}^n(1+\frac{p-1}{p^{x-2}}+\frac{p(p-1)}{p^{2(x-2)}}+\dots)\\ &=\prod_{i=1}^n\frac{1-p^{2-x}}{1-p^{3-x}}\\ &=\frac{\zeta(x-2)}{\zeta(x-3)}\\ \end{aligned}

于是有 g*I_2=I_3，然后 I_2,I_3 前缀和很好算，这个题就做完了。

感觉对我这种暴躁老哥+天生注意力涣散的人很友好。

给代码吗？给一个吧？

#include<bits/stdc++.h>
#define int __int128
#define maxn 5000000

using namespace std;

int cnt,prime[maxn+10],phi[maxn+10],sum[maxn+10],p,n,ans;
map < int ,int > m;
bool flag[maxn+10]; 

void predo(){
    flag[1]=1;
    phi[1]=1;
    for(int i=2;i<=maxn;++i){
        if(!flag[i]) prime[++cnt]=i,phi[i]=i-1;
//      cout<<(long long)i<<endl;
        for(int j=1;j<=cnt&&i*prime[j]<=maxn;++j){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0){
                (phi[i*prime[j]]=phi[i]*prime[j])%=p;
                break;
            }
            (phi[i*prime[j]]=phi[i]*phi[prime[j]])%=p;
        }
    }
//  cout<<"QAQ"<<endl;
    for(int i=1;i<=maxn;++i) (sum[i]=sum[i-1]+(i*i%p*phi[i])%p)%=p;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * f;
}

inline int sum2(int n){
    n%=p;
    return n*(n+1)*(2*n+1)/6%p;
}

inline int sum3(int n){
    n%=p;
    return (n*(n+1)/2%p)*(n*(n+1)/2%p)%p;
}

int getphi(int n){
    if(n<=maxn) return sum[n];
    if(m[n]) return m[n];
    int ans=sum3(n);
    for(int i=2,j;i<=n;i=j+1){
        j=n/(int)(n/i);
        ans-=(sum2(j)-sum2(i-1)+p)%p*getphi(n/i)%p;
        (ans+=p)%=p;
    }
    return m[n]=ans;
}

signed main(){
    p=read();
    n=read();   
    predo();
    for(int i=1,j;i<=n;i=j+1){
        j=(n/(n/i));
        ans+=sum3(n/i)*(getphi(j)-getphi(i-1)+p)%p;
        ans%=p;
    }
    long long tmp=ans;
    printf("%lld\n",tmp);
    return 0;
}