数学题单种树计划

数学 题解

---

改了标题之后里面的题目就杂起来了

那么问题来了 计算几何算不算数学题

loj556 「Antileaf's Round」咱们去烧菜吧

套路题

考虑某个不为$b_i\neq0$的物品的生成函数:

$$F_i(x)=\sum_{j=0}^{b_i}x^{ja_i}=\frac{1-x^{a_i(b_i+1)}}{1-x^{a_i}}$$
$b_i=0$的物品生成函数:
$$F_i(x)=\frac{1}{1-x^{a_i}}$$
最后的答案的生成函数:
$$\begin{aligned}{} G(x)&=\prod_{i=1}^nF_i(x)\\ \ln(G(x))&=\sum_{i=1}^n\ln(F_i(x))\\ &=\sum_{i=1}^n\ln(1-x^{a_i(b_i+1)})-\ln(1-x^{a_i})\\ \text{设}f(x)&=1-x^a\\ \text{而}\ln(f(x))&=\int \frac{f'(x)}{f(x)}dx=\int \frac{-ax^{a-1}}{1-x^a}dx\\ &=\int -ax^{a-1}\sum_{i=0}^{\infty}x^{ia}dx\\ &=\sum_{i=1}^{\infty}-\frac{x^{ai}}{i} \end{aligned}$$
给个代码:

signed main()
{
    read(n,m);
    for (int i = 1; i <= m; i++)
    {
        int a,b;
        read(a,b);
        if (a <= n) t[a] = (t[a] + 1) % mod;
        if (b && a * (b + 1) <= n) t[a * (b + 1)] = (t[a * (b + 1)] - 1 + mod) % mod;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)
            f[j] = (f[j] + t[i] * ksm(j / i,mod - 2) % mod) % mod;
    getexp(f,g,n + 1);
    for (int i = 1; i <= n; i++)
        writeln(g[i]);
    return 0;
}

loj6055 「from CommonAnts」一道数学题 加强版

神仙题 膜拜$\color{black}\text{f}\color{red}\text{ffxk}$ 众所周知 qy稳了

$$f(n,k)=\sum_{i=1}^{n-1}f(i,k)+n^k\\ f(n-1,k)=\sum_{i=1}^{n-2}f(i,k)+(n-1)^k\\ f(n,k)-f(n-1,k)=f(n-1,k)+n^k-(n-1)^k\\ f(n,k)=2f(n-1,k)+n^k-(n-1)^k\\ S(n,k)=\sum_{i=1}^nf(n,k)\\ S(n,k)-S(n-1,k)=f(n,k)=S(n-1,k)+n^k\\ S(n,k)=2S(n-1,k)+n^k=2^n\sum_{i=1}^{n}\frac{i^k}{2^i}\\ g(n,k)=\sum_{i=1}^n\frac{i^k}{2^i}$$
然后拿这个算就好了qaq

草这题的k怎么是2000啊 还要爆踩标算才行

给那题加强一下好了 我们要求的是:

$$f(n)=\sum_{i=1}^na^ii^k$$
我们不妨求出递推式:
$$f(n)=f(n-1)+a^nn^k\\ $$
这里有个 $n$ 在指数上 不能拉格朗日插值 我们考虑消除这个的影响 设出来一个函数:
$$\begin{aligned} g(n)&=\frac{f(n)+c}{a^n},\ g(0)=c\\ \text{那么}g(n-1)&=\frac{f(n-1)+c}{a^{n-1}}\\ g(n)&=\frac{f(n)+c}{a^n}=\frac{f(n-1)+a^nn^k+c}{a^n}=\frac{g(n-1)}{a}+n^k \end{aligned}$$
考虑对 $g$ 差分 方便地 我们定义 $g_t(x)$ 表示 $g$ 的 $t$ 阶差分:
$$\begin{aligned} g_1(n)&=\frac{1-a}{a}g(n-1)+n^k\\ g_2(n)&=g_1(n)-g_1(n-1)\\ &=\frac{1-a}{a}(g(n-1)-g(n-2))+n^k-(n-1)^k\\ &=\frac{1-a}{a}g_1(n-1)+P_2(n) \end{aligned}$$
注意到 $P_2(n)$ 的次数是 $k-1$ 次 而 $P_1(x)$ 即 $n^k$ 的次数是 $k$ 次 降了一次幂

那么 $P_{k+1}(n)=0$ 即 $g(k+1)=0$ 也就是 $g$ 的 $k+1$ 阶差分是 $0$

所以 $g$ 的通项是一个 $k$ 次的多项式 我们需要 $k+1$ 个点值来插值就可以得到 $g$ 的通项 最后就可以得到 $g(n)$

现在的问题转换成了如何求 $g(0)$ 这需要我们再次利用 $k+1$ 阶差分是$0$的特性:

$$\begin{aligned} g(x)&=\sum_{i=0}^{k+1}(-1)^i{k + 1\choose i}g_{k+1}(i)\\ g_{k+1}(i)&=\sum_{i=0}^{k+1}(-1)^i{k+1\choose i}g_i=0 \end{aligned}$$
而 $g(n)=h_n(g(0))$ 且$h_n$必然是一个一次函数 所以可以通过上式解出 $g_0$ 从而得到 $g_1,g_2,...,g_k$ 通过拉格朗日插值 得到$g_n$ 而 $f_n=a^ng(n)-f(0)$ 所以就可以得到$f_n$

复杂度是 $O(k)$ 我的实现下跑 $34ms$ 是当前的最优解 然而这个最优解第二的 $O(k^2)$ 跑了$71ms$(

给个最终的代码吧:

template <typename T>
void readb(T &a,T &b)
{
    T x = 0,f = 1,y = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = ((x << 1) + (x << 3) + (ch ^ 48)) % mod;
        y = ((y << 1) + (y << 3) + (ch ^ 48)) % (mod - 1);
        ch = getchar();
    }
    a = x * f;
    b = y * f;
}
struct line
{
    int k,t;
    line operator+(const line tmp) const
    {
        return (line) {(k + tmp.k) % mod,(t + tmp.t) % mod};
    }
    line operator-(const line tmp) const
    {
        return (line) {(k - tmp.k + mod) % mod,(t - tmp.t + mod) % mod};
    }
    line operator*(const int x) const
    {
        return (line) {k * x % mod,t * x % mod};
    }
}l[N];
int ksm(int a,int b,int mod = mod)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int C(int n,int m)
{
    if (n < m) return 0;
    if (n < 0 || m < 0) return 0;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
int clac(int n)
{
    if (n <= k + 1) return g[n];
    int ans = 0,res = 1;
    for (int i = 1; i <= k + 1; i++)
        res = res * (n - i) % mod;
    for (int i = 1; i <= k + 1; i++)
    {
        int tmp = inv[i - 1] * inv[k + 1 - i] % mod;
        ans = (ans + g[i] * tmp % mod * res % mod * ksm(n - i,mod - 2) % mod * ((k + 1 - i) & 1 ? -1 : 1) + mod) % mod;
    }
    return ans;
}
int getf(int n,int _n)
{
    return (ksm(a,_n) * clac(n) % mod - g[0] + mod) % mod;
}
int getsum(int n,int _n)
{
    int ans = getf(n,_n);
    return ans * ksm(2,_n) % mod;
}
signed main()
{
    a = ksm(2,mod - 2);
    readb(n,_n);
    read(k);
    fac[0] = inv[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = ksm(fac[N - 1],mod - 2);
    for (int i = N - 1; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    idk[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i]) pri[++cnt] = i,idk[i] = ksm(i,k);
        for (int j = 1; j <= cnt && i * pri[j] < N; j++)
        {
            vis[i * pri[j]] = 1;
            idk[i * pri[j]] = idk[i] * idk[pri[j]] % mod;
            if (!(i % pri[j])) break;
        }
    }
    l[0] = (line) {1,0};
    for (int i = 1; i <= k + 1; i++)
        l[i] = l[i - 1] * 2 + (line) {0,idk[i] % mod};
    line res = (line) {0,0};
    for (int i = 0; i <= k + 1; i++)
    {
        if (i & 1) res = res - l[k + 1 - i] * C(k + 1,i);
        else res = res + l[k + 1 - i] * C(k + 1,i);
    }
    g[0] = (mod - res.t * ksm(res.k,mod - 2) % mod) % mod;
    for (int i = 1; i <= k + 5; i++)
        g[i] = (2 * g[i - 1] + idk[i]) % mod;
    writeln((getsum(n,_n) - getsum(n - 1,(_n - 1 + mod - 1) % (mod - 1)) + mod) % mod);
    return 0;
}

loj6391 「THUPC2018」淘米神的树 / Tommy

8会

loj6609 无意识的石子堆 加强版

看着是可做题

首先考虑题意转换成为一个左边 $n$ 个点右边 $m$ 个点 $2n$ 条边的有标号二分图计数 满足所有点的度 $d\leq 2$

而事实上 每行都会有 $2$ 个棋子 所以:

$$ans=\sum_{i=0}^n{m\choose i}{m - i \choose 2(n-i)}S_i$$
$S_i$ 是这个二分图的完美匹配数量:
$$S_i=\frac{1}{2^{n+i}}\sum_{j=0}^i(-1)^jj!{i \choose j}{n\choose j}2^j(2n-2j)!$$
给个实现:

signed main()
{
    read(n,m);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n << 1; i++)
        fac[i] = fac[i - 1] * i % mod;
    inv[n << 1] = ksm(fac[n << 1],mod - 2);
    for (int i = n << 1; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    for (int i = 0; i <= n; i++)
        f[i] = ksm(mod - 1,i) * fac[(n - i) << 1] % mod * C(n,i) % mod * ksm(2,i) % mod;
    for (int i = 0; i <= n; i++)
        g[i] = inv[i];
    lim = 1;
    while (lim <= n + n) lim <<= 1;
    getr(lim);
    ntt(f,1);
    ntt(g,1);
    for (int i = 0; i < lim; i++) f[i] = f[i] * g[i] % mod;
    ntt(f,-1);
    down[0] = 1;
    for (int i = 1; i <= n << 1; i++)
        down[i] = down[i - 1] * ((m - i + 1) % mod) % mod;
    int ans = 0;
    for (int i = 0; i <= n; i++)
        ans = (ans + down[n + n - i] * fac[i] % mod * ksm(ksm(2,n + i),mod - 2) % mod * f[i] % mod * inv[i] % mod * inv[(n - i) << 1] % mod) % mod;
    writeln(ans);
    return 0;
}

loj6703 小 Q 的序列

考虑一个$dp$ $dp[i][j]$表示到$i$个数 之前选了$j$个数的价值和 有转移:

$$dp[i][j]=(j+a_i)\times dp[i-1][j-1]+dp[i-1][j]$$
考虑优化这个$n^2$的式子 看着很像是斯特林数的递推式 我们考虑仿照斯特林数的做法来推一下这个式子的递推

尝试换一种写法$dp[i][j]$表示前$i$个数中有$j$个不选的价值和:

$$dp[i][j]=dp[i-1][j]\times(i-j+a_i)+dp[i-1][j-1]$$
阴间组合意义考虑$i$个数放入$j$个盒子中:

一个位置的数有$3$种情况:不选($(a_i+i)dp[i-1][j]$) 或者加入一个集合($-jdp[i-1][j]$) 或者新开一个集合($dp[i-1][j-1]$)

一个数给你乘$a_i+i$的贡献相当于这个位置上的数不选

我们不妨拆开贡献 将选$i$个数不选的贡献先求出来 这个的贡献:

$$F(x)=\prod_{i=1}^n(1+(a_i+i)x)$$
钦定了不选的数之后考虑放入的问题

我们设:$f_{i,j}$表示$i$个数中按照上述贡献分成$j$个集合的价值

显然有$f_{i,j}=-jf_{i-1,j}+f_{i-1,j-1}$ 我们假设$g_{i,j}=f_{i,j}(-1)^i$ 那么$g_{i,j}=-g_{i - 1,j - 1}+jg_{i - 1,j}$

写出这个$g_{i,j}$的EGF:

$$G_j(x)=\frac{(1-e^x)^j}{j!}$$
而我们的答案是:
$$ans=\sum_{i=0}^n[x^i]F(x)\sum_{j=1}^{n-i}f_{n-i,j}$$
所以考虑$\sum\limits_{j=1}^{i}g_{i,j}$ 的EGF 就是:
$$G(x)=e^{1-e^x}$$
给个实现:

void cdq(poly &f,int l,int r)
{
    if (l == r)
    {
        f.resize(r - l + 2);
        f[0] = 1;
        f[1] = (a[l] + l) % mod;
        return ;
    }
    int mid = (l + r) >> 1;
    poly A,B;
    cdq(A,l,mid);
    cdq(B,mid + 1,r);
    lim = 1;
    while (lim <= (r - l + 1)) lim <<= 1;
    getr(lim);
    ntt(A,1);
    ntt(B,1);
    f.resize(lim);
    for (int i = 0; i < lim; i++) f[i] = A[i] * B[i] % mod;
    ntt(f,-1);
    f.resize(r - l + 2);
}
signed main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    cdq(f,1,n);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    inv[n] = ksm(fac[n],mod - 2);
    for (int i = n; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    for (int i = 1; i <= n; i++)
        g[i] = mod - inv[i];
    getexp(g,h,n + 1);
    for (int i = 0; i <= n; i++)
        h[i] = h[i] * fac[i] % mod;
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        int qaq = n - i;
        if (qaq & 1) ans = (ans - f[i] * h[qaq] % mod + mod) % mod;
        else ans = (ans + f[i] * h[qaq] % mod) % mod;
    }
    writeln(ans - 1);
    return 0;
}

loj6247 九个太阳

高质量板子题(?)

$$\begin{aligned} \sum_{i=0}^n{n \choose i}[k|i]&=\sum_{i=0}^n{n\choose i}\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{ij}\\ &=\frac{1}{k}\sum_{i=0}^n {n\choose i}\sum_{j=0}^{k-1}\omega_k^{ij}\\ &=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^{n}{n \choose i}\omega_k^{ij}\\ &=\frac{1}{k}\sum_{i=0}^{k-1}(\omega_k^i+1)^n \end{aligned}$$
给个实现好了

signed main()
{
    read(n,k);
    int w = ksm(3,(mod - 1) / k);
    int wn = 1,ans = 0;
    for (int i = 0; i < k; i++)
    {
        ans = (ans + ksm(wn + 1,n)) % mod;
        wn = wn * w % mod;
    }
    writeln(ans * ksm(k,mod - 2) % mod);
    return 0;
}

AGC005F Many Easy Problems

套路地考虑对于点对于 $f(k)$ 的贡献 有这个式子:

$$\begin{aligned} f(k)&=\sum_{u=1}^n{n\choose k}-\sum_{v \in son_u}{siz_v\choose k}\\ &=n{n\choose k}-\sum_{u=1}^n\sum_{v \in son_u}{siz_v\choose k}\\ &=n{n \choose k}-\sum_{i=k}^n{i \choose k}cnt_i\\ &=n{n\choose k}-\frac{1}{k!}\sum_{i=k}^n\frac{cnt_i i!}{(i-k)!} \end{aligned}$$
设 $F(x)=cnt_xx!,\ G(x)=\frac{1}{x!}$ 把上式改写成:
$$f(k)=n{n\choose k}-\frac{1}{k!}\sum_{i=0}^{n-k}F(i+k)G(i)$$
翻转 $F(x)$ 之后用ntt加速即可 给个实现:

void dfs(int u,int f)
{
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = pnt[i];
        if (v == f) continue;
        dfs(v,u);
        siz[u] += siz[v];
        cnt[siz[v]]++;
    }
    cnt[n - siz[u]]++;
}
signed main()
{
    memset(head,-1,sizeof(head));
    memset(cnt,0,sizeof(cnt));
    read(n);
    for (int i = 1; i < n; i++)
    {
        int u,v;
        read(u,v);
        add_edge(u,v);
        add_edge(v,u);
    }
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    dfs(1,0);
    for (int i = 1; i <= n; i++)
        f[i] = cnt[i] * fac[i] % mod;
    reverse(f,f + n + 1);
    for (int i = 0; i <= n; i++)
        g[i] = ifac[i];
    lim = 1;
    while (lim <= (n << 1)) lim <<= 1;
    getr(lim);
    ntt(f,1);
    ntt(g,1);
    for (int i = 0; i < lim; i++)
        f[i] = f[i] * g[i] % mod;
    ntt(f,-1);
    reverse(f,f + n + 1);
    for (int i = 1; i <= n; i++)
        writeln((n * C(n,i) % mod - ifac[i] * f[i] % mod + mod) % mod);
    return 0;
}

CF1096G Lucky Tickets

好像是个憨憨题诶

考虑计算出 $\frac{n}{2}$ 位可以得到的数位的和以及对应的方案数 那么答案就是:

$$\sum_{i=0}^{5n}f_i^2$$
写出对应的生成函数:
$$F(x)=\sum_{i=0}^9 a_ix^{i}$$
那么最后我们要的生成函数就是 $F^\frac{n}{2}(x)$

我竟然找到了多项式快速幂的应用（

然后我就头铁写ln+exp的卡了一下午常

没想到吧 exp能跑1e6!甚至不是最慢解

loj2541 「PKUWC2018」猎人杀

考虑容斥,不合法的答案是有一些数在1之后才被删除

定义全集$A=\{2,3,...,n\}$,以及令$sum=\displaystyle\sum\limits_{i=1}^n\omega_i$

那么我们很容易得到这样一个不合法概率的式子:

$$\begin{aligned} &\displaystyle\sum\limits_{S\subset A}\displaystyle\sum\limits_{i=0}^{\infty}(-1)^{|S|}\left(\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}\right)^i\cfrac{\omega_1}{sum}\\ &=\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\displaystyle\sum\limits_{i=0}^{\infty}\left(\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}\right)^i\\ \end{aligned}$$

而我们知道:

$$1+x+x^2+...+x^{n-1}+x^n+...=\frac{1}{x-1}$$

所以我们可以得到:

$$\begin{aligned} &\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\displaystyle\sum\limits_{i=0}^{\infty}\left(\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}\right)^i\\ &=\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\frac{1}{\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}-1}\\ &=-\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\frac{sum}{\omega_1+\displaystyle\sum\limits_{x\in S}\omega_x}\\ \end{aligned}$$

我们考虑套路地更换枚举顺序:

$$-\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\frac{sum}{\omega_1+\displaystyle\sum\limits_{x\in S}\omega_x}\\ =-\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{x=1}^{sum-\omega_1}\frac{sum}{\omega_1+x}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x]\\ =-\displaystyle\sum\limits_{x=1}^{sum-\omega_1}\frac{\omega_1}{\omega_1+x}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x] \tag{1}$$

我们考虑后面地这个东西应该如何计算,不妨考虑他的生成函数:

$$F(x)=\displaystyle\prod_{i=2}^n(1-x^{\omega_i})\tag{2}$$

对于某个数$i$,$1$表示不选这个数,而$x^{\omega_i}$表示选这个数,那么我们所要的式子就是:

$$\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x]=[x^n]F(x)$$
我们观察数据范围,发现(1)可以直接暴力乘法得到,所以我们只需要考虑(2)式.

(2)式的处理我们考虑一个分治,并不是分治fft,只是单纯地每次将其分成两部分,再将两部分合并

所以我们要的答案就是:

$$1+\displaystyle\sum\limits_{x=1}^{sum-\omega_1}\frac{\omega_1}{\omega_1+x}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x]$$
给个卡常之后的丑陋实现

CF438E The Child and Binary Tree

考虑如何计算和为 $x$ 的方案数:

$$f(x)=\sum_{i\in C}\sum_{j=1}^{x-i}f(j)f(x-i-j)$$
我们做以下定义:
$$f(x)\text{ 的生成函数为 }F(x)\\ g(x)=[x\in C]\text{ 的生成函数为 }G(x)\\ h(x)=\sum_{j=1}^{x}f(j)f(x-j) \text{ 的生成函数为} H(x) = F^2(x)$$
我们有:
$$F(x)=G(x)F^2(x)+1\\ F_1(x)=\frac{1+\sqrt{1-4G(x)}}{2G(x)},F_2(x)=\frac{1-\sqrt{1-4G(x)}}{2G(x)}$$
显然 $F_2(x)$ 符合题意 但是这个 $G(x)$ 的常数项是0 难以计算 所以我们需要分母无理化:
$$F(x)=\frac{2}{1+\sqrt{1-4G}}$$
可以上板子直接算了

signed main()
{
    read(n,m);
    m++;
    for (int i = 1; i <= n; i++)
    {
        int x;
        read(x);
        if (x < m) g[x] = mod - 4;
    }
    g[0]++;
    getsqrt(g,h,m);
    h[0]++;
    getinv(h,f,m);
    for (int i = 1; i < m; i++)
        writeln(2 * f[i] % mod);
    return 0;
}

ARC096C Everything on It

考虑一个容斥 我们设 $f(x)$ 表示至少有 $x$ 个数出现次数小于等于 1 那么:

$$ans = \sum_{i=0}^n(-1)^if(i)$$
对于其他 $n - x$ 个数没有限制 这部分的方案数是 $2^{2^{n - x}}$ 而对于 $x$ 的选择 方案数是 ${n \choose x}$

现在的问题是 $x$ 个数出现次数小于等于 1 的方案数

我们把这个方案数设出来 设为 $g(x)$

对于选出的一个元素 $i$ 讨论 有两种情况:

1. 不出现
2. 仅出现一次

假设没有第一种情况 那方案数就是一行斯特林数的和 考虑转化问题 我们认为不出现的元素只是出现在了一个 假定的集合 中 此时我们添加一个标记元素 包含这个元素的集合就是假定集合

那么我们就可以计算 $g(x)$ 了:

$$g(x)=\sum_{i=0}^x \left\{x + 1\atop i + 1\right\}2^{i(n-x)}$$
把最后的答案写出来:
$$ans=\sum_{i=0}^n(-1)^i2^{2^{n - i}}{n \choose i} \sum_{j=0}^i \left\{i + 1\atop j + 1\right\} 2^{j(n-i)}$$
$\mathcal O(n^2)$ 递推 Stirling 数即可

signed main()
{
    read(n,mod);
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    s[0][0] = 1;
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= i; j++)
            s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j] % mod) % mod;
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        int res = 0;
        for (int j = 0; j <= i; j++)
            res = (res + s[i + 1][j + 1] * ksm(2,j * (n - i)) % mod) % mod;
        res = res * C(n,i) % mod * ksm(2,ksm(2,n - i,mod - 1)) % mod;
        if (i & 1) ans = (ans - res + mod) % mod;
        else ans = (ans + res) % mod;
    }
    writeln(ans);
    return 0;
}

CF923E Perpetual Subtraction

考虑一个 $\mathcal O(nm)$ 的 dp: $f_{i,j}$ 表示 $i$ 轮前 数为 $j$ 的概率

那么有转移:

$$f_{i,j}=\sum_{k=j}^{n} \frac{f_{i-1,k}}{k + 1}$$
快进到生成函数:
$$\begin{aligned} F_i(x)&=\sum_{j=0}^nf_{i,j}x^j\\ &=\sum_{j=0}^nx^{j}\sum_{k=j}^n\frac{f_{i-1,k}}{k+1}\\ &=\sum_{k=0}^n\frac{f_{i-1,k}}{k+1}\sum_{j=0}^kx^j\\ &=\sum_{k=0}^n\frac{f_{i-1,k}}{k+1}\frac{x^{k+1}-1}{x-1}\\ &=\frac{1}{x-1}{\sum_{k=0}^n\frac{f_{i-1,k}}{k+1}(x^{k+1}-1)}\\ &=\frac{1}{x-1}\int_1^x F_{i-1}(t)dt\\ &=\frac{1}{x-1}\int_0^{x-1} F(t+1)d(t+1) \end{aligned}$$
为了方便 我们设出一个生成函数 $G_i(x)=F_i(x+1)$ 有:
$$G_i(x)=\frac{1}{x}\int_0^x G_{i-1}(x) dx=\sum_{j=0}^n\frac{g_{i-1,j}}{j+1}x^j$$
所以我们可以得到:
$$g_{i,j}=\frac{g_{i-1,j}}{j+1}=(\frac{1}{j+1})^{i-1}g_{1,j}$$
而 $G_i(x)=F_i(x+1)$ 即:
$$\begin{aligned} \sum_{j=0}^ng_{i,j}x^j&=\sum_{j=0}^nf_{i,j}\sum_{k=0}^j {j\choose k}x^k\\ \sum_{j=0}^ng_{i,j}x^j&=\sum_{k=0}^nx^k\sum_{j=k}^nf_{i,j}{j\choose k}\\ g_{i,j}&=\sum_{k=j}^n{k\choose j}f_{i,k} \end{aligned}$$
对应的 此时:
$$g_{1,j}=\sum_{k=j}^n{k\choose j}f_{1,k}=\sum_{k=j}^n\frac{k!p_k}{(k - j)!j!}=\frac{1}{j!}\sum_{k=j}^n\frac{k!p_k}{(k - j)!}$$
翻转后 ntt 加速求 $g_{1,j}$ 我们便可求出 $g_{m+1,j}$ 再求 $f_{m+1,j}$ 考虑二项式反演:
$$\begin{aligned} g_{m+1,j}&=\sum_{k=j}^n{k\choose j}f_{m+1,k}\\ f_{m+1,j}&=\sum_{k=j}^n (-1)^{k-j} {k\choose j}g_{m+1,k}\\ &=\sum_{k=j}^n(-1)^{k-j}\frac{k!g_{m+1,k}}{(k - j)!j!}\\ &=\frac{1}{j!}\sum_{k=j}^n(-1)^{k-j}\frac{k!g_{m+1,k}}{(k-j)!} \end{aligned}$$
将其中一个翻转后 同样 ntt 加速即可

总复杂度 $\mathcal O(n\log n)$

signed main()
{
    read(n,m);
    m %= mod - 1;
    for (int i = 0; i <= n; i++)
        read(p[i]);
    inv[1] = 1;
    for (int i = 2; i <= n + 1; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n + 1; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    for (int i = 0; i <= n; i++)
        f[i] = ifac[i],g[i] = p[n - i] * fac[n - i] % mod;
    lim = 1;
    while (lim < (n << 1) + 1) lim <<= 1;
    getr(lim);
    ntt(f,1);
    ntt(g,1);
    for (int i = 0; i < lim; i++) g[i] = f[i] * g[i] % mod;
    ntt(g,-1);
    for (int i = 0; i <= n; i++)
        g[n - i] = ksm(inv[i + 1],m) * g[n - i] % mod;
    for (int i = 0; i <= n; i++)
    {
        if (i & 1) f[i] = mod - ifac[i];
        else f[i] = ifac[i];
    }
    for (int i = n + 1; i < lim; i++)
        f[i] = g[i] = 0;
    ntt(f,1);
    ntt(g,1);
    for (int i = 0; i < lim; i++) f[i] = f[i] * g[i] % mod;
    ntt(f,-1);
    reverse(f,f + n + 1);
    for (int i = 0; i <= n; i++)
        writes(f[i] * ifac[i] % mod);
    puts("");
    return 0;
}

bzoj1815 [Shoi2006]color 有色图

经典题

根据 Polya 我们可以知道:

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|S|^{c(g)}$$
置换的总数显然是 $n!$

考虑怎么求 $c(g)$ 事实上我们好处理的置换是点的置换而非边的置换 所以考虑拆分点的置换

把点的置换 $g$ 拆分成 $a_1,a_2,\dots a_{cnt}$ 这 $cnt$ 个的循环

边的两点分成两种:

1. 在不同的循环中
2. 在同一循环中

对于第一种情况 不妨考虑循环长度 对于循环 $a_i$ 和 $a_j$ 这之间连边的循环长度显然是 $\operatorname{lcm}(a_i,a_j)$ 那么循环的数量 $c(g)$ 就是 $\frac{a_ia_j}{\operatorname{lcm}(a_i,a_j)}=\gcd(a_i,a_j)$

考虑第二种情况 长度相等的边属于同一个等价类 所以有 $\lfloor\frac{a_i}{2}\rfloor$ 种

考虑这样的拆分会对应多少个置换:

$$\frac{n!}{\prod\limits_{i=1}^{cnt}a_i}$$
具体地考虑 把 $n$ 放入 $cnt$ 个至多放 $b_i$ 的环中 显然有:
$$\frac{n!}{\prod\limits_{i=1}^{cnt}a_i!}\prod_{i=1}^{cnt}(a_i-1)!$$
显然我们并不能去暴力枚举 我们应该把长度相等的压在一起计算

那么我们改写我们的最终的式子:

$$\frac{n!}{\prod\limits_{i=1}^{cnt}a_i^{c_i}c_i!}m^{\sum\limits_{i=1}^{cnt}c_i\lfloor\frac{a_i}{2}\rfloor+\sum\limits_{1\leq i < j \leq cnt}c_ic_j\gcd(a_i,a_j)}$$
我们直接爆拆分拆数计算 注意最后我们还要除以 $n!$ 就是了

代码:

void clac(int cnt)
{
    int res = 0;
    for (int i = 1; i <= cnt; i++)
    {
        res = (res + a[i] / 2 * c[i] % (mod - 1)) % (mod - 1);
        res = (res + c[i] * (c[i] - 1) / 2 % (mod - 1) * a[i] % (mod - 1)) % (mod - 1);
        for (int j = 1; j < i; j++)
            res = (res + gcd(a[i],a[j]) * c[i] % (mod - 1) * c[j] % (mod - 1)) % (mod - 1);
    }
    res = ksm(m,res);
    for (int i = 1; i <= cnt; i++)
        res = res * ksm(inv[a[i]],c[i]) % mod * ifac[c[i]] % mod;
    ans = (ans + res) % mod;
}
void dfs(int n,int id,int mini)
{
    if (!n) return clac(id - 1);
    for (int i = mini + 1; i <= n; i++)
    {
        a[id] = i;
        c[id] = 0;
        for (int j = i; j <= n; j += i)
            c[id]++,dfs(n - j,id + 1,i);
    }
}
signed main()
{
    read(n,m,mod);
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    dfs(n,1,0);
    writeln(ans);
    return 0;
}

CF755G PolandBall and Many Other Balls

考虑一个 dp:

$dp_{i,j}$ 表示前 $i$ 个球取出 $j$ 组的方案数 有转移:

$$dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}+dp_{i-2,j-1}$$
我们把生成函数设出来 定义:
$$F_{n}(x)=\sum_{i=0}^ndp_{n,i}x^i$$
那么有:
$$F_n(x)=F_{n-1}(x)+xF_{n-1}(x)+xF_{n-2}(x)=(1+x)F_{n-1}(x)+xF_{n-2}(x)$$
快进到特征方程:
$$t^2-(1+x)t-x=0$$
得到特征根:
$$t_1=\frac{1+x+\sqrt{\Delta}}{2},t_2=\frac{1+x-\sqrt{\Delta}}{2}$$
其中: $\Delta=x^2+6x+1$

套路地 设出通项公式为:

$$F_n(x)=at_1^{n+1}+bt_2^{n+1}$$
而我们知道的是: $F_1(x)=1+x,F_2(x)=1+3x+x^2$

我们可以带入解方程 得到:

$$F_n(x)=\frac{t_1^{n+1}+t_2^{n+1}}{\sqrt{\Delta}}$$

signed main()
{
    read(n,k);
    k++;
    f[0] = 1,f[1] = 6,f[2] = 1;
    getsqrt(f,delta,k);
    for (int i = 0; i < k; i++)
        t1[i] = delta[i] * INV % mod,t2[i] = (mod - delta[i]) * INV % mod,f[i] = 0;
    t1[0] = (t1[0] + INV) % mod,t1[1] = (t1[1] + INV) % mod;
    t2[0] = (t2[0] + INV) % mod,t2[1] = (t2[1] + INV) % mod;
    getksm(t1,f,k,n + 1,n + 1,(int) (log(n + 1) / log(10)));
    getksm(t2,g,k,n + 1,n + 1,(int) (log(n + 1) / log(10)));
    getinv(delta,h,k);
    for (int i = 0; i < k; i++)
        f[i] = (f[i] + g[i]) % mod;
    lim = 1;
    while (lim < (k << 1) - 1) lim <<= 1;
    getr(lim);
    ntt(f,1);
    ntt(h,1);
    for (int i = 0; i < lim; i++) f[i] = f[i] * h[i] % mod;
    ntt(f,-1);
    for (int i = 1; i < k && i <= n; i++)
        writes(f[i]);
    for (int i = n + 1; i < k; i++)
        putchar('0'),putchar(' ');
    puts("");
    return 0;
}

CF1295F Good Contest

确认过 是个套路题

首先有一个很显然的 dp : $dp_{i,j}$ 表示前 $i$ 个数 最后一个数是 $j$ 的方案数

显然不行的是 值域很大 但是 $n$ 很小 所以可以考虑离散化后对于一个左闭右开区间进行 dp

考虑 $dp_{i,j}$ 表示前 $i$ 个数 最后那个数在 $j$ 区间的方案数

转移时考虑枚举在 $j$ 区间内的数的个数 然后统计答案

signed main()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        read(l[i],r[i]);
        r[i]++;
        id[++cnt] = l[i];
        id[++cnt] = r[i];
    }
    sort(id + 1,id + cnt + 1);
    cnt = unique(id + 1,id + cnt + 1) - id - 1;
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(id + 1,id + cnt + 1,l[i]) - id;
        r[i] = lower_bound(id + 1,id + cnt + 1,r[i]) - id;
    }
    for (int i = 1; i <= cnt; i++) dp[0][i] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = l[i]; j < r[i]; j++)
        {
            int len = id[j + 1] - id[j];
            for (int k = i; k >= 1; k--)
            {
                if (j < l[k] || r[k] <= j) break;
                dp[i][j] = (dp[i][j] + dp[k - 1][j + 1] * C(i - k + len,i - k + 1) % mod) % mod;
            }
        }
        for (int j = cnt - 1; j >= 1; j--)
            dp[i][j] = (dp[i][j] + dp[i][j + 1]) % mod;
    }
    for (int i = 1; i <= n; i++)
        dp[n][1] = dp[n][1] * ksm(id[r[i]] - id[l[i]],mod - 2) % mod;
    writeln(dp[n][1]);
    return 0;
}

CF997C Sky Full of Stars

考虑: $f(i,j)$ 表示 恰好有 $i$ 行 $j$ 列同色的方案数 $g(i,j)$ 表示 至少有 $i$ 行 $j$ 列同色的方案数

那么显然有:

$$g(x,y)=\sum_{i=x}^n\sum_{j=y}^n {i\choose x} {j\choose y} f(i,j)$$
考虑二项式反演:
$$f(x,y)=\sum_{i=x}^n\sum_{j=y}^n(-1)^{i+j-x-y}{i\choose x}{j\choose y}g(i,j)$$
而我们最终的答案是:
$$ans=3^{n^2}-f(0,0)=3^{n^2}-\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}g(i,j)$$
问题转化成了如何求 $g(i,j)$ 为了方便我们钦定同色的行列位置 但是 $i$ 或 $j$ 为 $0$ 的时候要分讨
$$g(x,y)= \begin{cases} 3^{n^2}& x+y=0\\ {n\choose x+y}3^{n(n-x-y)+x+y}& xy=0,x+y\neq0\\ {n\choose x}{n\choose y}3^{(n-x)(n-y)+1}& xy\neq0 \end{cases}$$
代回原来的式子:
$$ans=3^{n^2}-\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}{n\choose i}{n\choose j}3^{(n-i)(n-j)+1}-2\sum_{i=1}^n(-1)^i{n\choose i}3^{n(n-i)+i}-3^{n^2}$$
我们需要化简的是中间那个式子 单独拿出来处理:
$$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}{n\choose i}{n\choose j}3^{(n-i)(n-j)+1}&=\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}{n\choose i}{n\choose j}3^{n^2-(i+j)n+ij+1}\\ &=3^{n^2+1}\sum_{i=1}^n(-1)^i{n\choose i}3^{-in}\sum_{j=1}^n(-1)^{j}{n\choose j}(3^{i-n})^j\\ &=3^{n^2+1}\sum_{i=1}^n(-1)^i{n\choose i}3^{-in}((1-3^{i-n})^n-1) \end{aligned}$$
最后把式子写一遍:
$$ans=-3^{n^2+1}\sum_{i=1}^n(-1)^i{n\choose i}3^{-in}((1-3^{i-n})^n-1)-2\sum_{i=1}^n(-1)^i{n\choose i}3^{n(n-i)+i}$$
复杂度 $\mathcal O(n\log n)$ 可以通过本题

signed main()
{
    read(n);
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i & 1) ans = (ans - C(n,i) * ksm(ksm(3,(i * n) % (mod - 1)),mod - 2) % mod * (ksm(1 - ksm(ksm(3,n - i),mod - 2) + mod,n) - 1) % mod + mod) % mod;
        else ans = (ans + C(n,i) * ksm(ksm(3,(i * n) % (mod - 1)),mod - 2) % mod * (ksm(1 - ksm(ksm(3,n - i),mod - 2) + mod,n) - 1) % mod) % mod;
    }
    ans = ans * ksm(3,(n * n + 1) % (mod - 1));
    for (int i = 1; i <= n; i++)
    {
        if (i & 1) ans = (ans - 2 * C(n,i) * ksm(3,(n * (n - i) + i) % (mod - 1)) + mod) % mod;
        else ans = (ans + 2 * C(n,i) * ksm(3,(n * (n - i) + i) % (mod - 1))) % mod;
    }
    writeln((mod - ans) % mod);
    return 0;
}

uoj419 【集训队作业2018】圆形

首先考虑圆的面积并怎么做 考虑格林公式:

$$\iint\limits_{D}(\frac{\operatorname{\partial}Q}{\operatorname{\partial}x}-\frac{\operatorname{\partial}P}{\operatorname{\partial}y})\operatorname{d}x\operatorname{d}y=\oint\limits_{L^+}P\operatorname{d}x+Q\operatorname{d}y$$
区域 $D$ 的面积是:
$$\iint\limits_{D}\operatorname{d}x\operatorname{d}y=\oint\limits_{L^+}x\operatorname{d}x=-\oint\limits_{L^+}y\operatorname{d}y=\frac{1}{2}\oint\limits_{L^+}x\operatorname{d}x-y\operatorname{d}y$$
考虑设 $Q=x$ 或 $P=-y$ 则可以得到上式 现在考虑三角代换 设:$x=x_0+r\cos\theta$ $y=y_0+r\sin\theta$
$$\begin{aligned} &\oint\limits_{L^+}(x_0+r\cos\theta)\operatorname{d}\theta\frac{\operatorname{d}x}{\operatorname{d}\theta}-(y_0+r\sin\theta)\operatorname{d}\theta\frac{\operatorname{d}y}{\operatorname{d}\theta}\\ &=\int\limits_{L^+}(x_0+r\cos\theta)r\cos\theta\operatorname{d}\theta-(y_0+r\sin\theta)r\sin\theta\operatorname{d}\theta\\ &=r(r(\phi_1-\phi_2)+x_0(\sin\phi_1-\sin\phi_2)-y_0(\cos\phi_1-\cos\phi_2)) \end{aligned}$$
然后动态维护圆弧 求和

const long double eps = 1e-11,pi = acos(-1.0);
int n,vis[N];
long double sqr(long double x)
{
    return x * x;
}
struct point
{
    long double x,y;
    bool operator<(const point &tmp) const
    {
        if (x != tmp.x) return x + eps < tmp.x;
        return y + eps < tmp.y;
    }
    bool operator==(const point &tmp) const
    {
        return fabs(x - tmp.x) <= eps && fabs(y - tmp.y) <= eps;
    }
    bool operator!=(const point &tmp) const
    {
        return !(fabs(x - tmp.x) <= eps && fabs(y - tmp.y) <= eps);
    }
    point operator+(const point &tmp) const
    {
        return (point) {x + tmp.x,y + tmp.y};
    }
    point operator-(const point &tmp) const
    {
        return (point) {x - tmp.x,y - tmp.y};
    }
    long double angle()
    {
        return atan2(y,x);
    }
};
struct cir
{
    point o;
    long double r;
    bool operator<(const cir &tmp) const
    {
        if (o != tmp.o) return o < tmp.o;
        return r < tmp.r;
    }
    bool operator==(const cir &tmp) const
    {
        return o == tmp.o && fabs(r - tmp.r) <= eps;
    }
    long double oint(long double phi2,long double phi1)
    {
        return (r * (phi1 - phi2) + o.x * (sin(phi1) - sin(phi2)) - o.y * (cos(phi1) - cos(phi2))) * r;
    }
}a[N];
struct node
{
    long double l,r;
    bool operator<(const node &tmp) const
    {
        return r + eps < tmp.r;
    }
};
set<node> s[N];
bool in(cir x,cir y)
{
    point tmp = x.o - y.o;
    return sqr(tmp.x) + sqr(tmp.y) <= sqr(y.r - x.r);
}
bool out(cir x,cir y)
{
    point tmp = x.o - y.o;
    return sqr(tmp.x) + sqr(tmp.y) >= sqr(x.r + y.r);
}
long double update(int id,long double l,long double r)
{
    long double res = 0;
    set<node>::iterator it2;
    for (set<node>::iterator it = s[id].lower_bound((node) {0,l}); it != s[id].end() && it -> l < r; it = it2)
    {
        long double nowl = it -> l,nowr = it -> r;
        it2 = it;
        it2++;
        s[id].erase(it);
        res -= a[id].oint(nowl,nowr);
        if (nowl < l) res += a[id].oint(nowl,l),s[id].insert((node) {nowl,l});
        if (nowr > r) res += a[id].oint(r,nowr),s[id].insert((node) {r,nowr});
    }
    return res;
}
signed main()
{
    read(n,n);
    for (int i = 1; i <= n; i++)
        scanf("%Lf%Lf%Lf",&a[i].o.x,&a[i].o.y,&a[i].r);
    long double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (in(a[i],a[j]) && a[j].r >= a[i].r)
            {
                vis[i] = 0;
                break;
            }
            if (in(a[j],a[i]) && a[i].r >= a[j].r)
            {
                vis[j] = 0;
                ans += update(j,-pi,pi);
            }
        }
        if (!vis[i])
        {
            printf("%.10Lf\n",ans * 0.5);
            continue;
        }
        ans += a[i].oint(-pi,pi);
        s[i].insert((node) {-pi,pi});
        for (int j = 1; j < i; j++)
        {
            if (!vis[j] || out(a[i],a[j])) continue;
            point qaq = a[i].o - a[j].o;
            long double dis = sqrt(sqr(qaq.x) + sqr(qaq.y)),alpha = qaq.angle();
            long double beta = acos((sqr(dis) + sqr(a[j].r) - sqr(a[i].r)) / (2.0 * dis * a[j].r));
            long double l = alpha - beta,r = alpha + beta;
            if (l < -pi) l += 2.0 * pi;
            if (l > pi) l -= 2.0 * pi;
            if (r < -pi) r += 2.0 * pi;
            if (r > pi) r -= 2.0 * pi;
            if (l < r) ans += update(j,l,r);
            else ans += update(j,-pi,r),ans += update(j,l,pi);
            qaq = a[j].o - a[i].o;
            alpha = qaq.angle();
            beta = acos((sqr(dis) + sqr(a[i].r) - sqr(a[j].r)) / (2.0 * dis * a[i].r));
            l = alpha - beta,r = alpha + beta;
            if (l < -pi) l += 2.0 * pi;
            if (l > pi) l -= 2.0 * pi;
            if (r < -pi) r += 2.0 * pi;
            if (r > pi) r -= 2.0 * pi;
            if (l < r) ans += update(i,l,r);
            else ans += update(i,-pi,r),ans += update(i,l,pi);
        }
        printf("%.10Lf\n",ans * 0.5);
    }
    return 0;
}

CF848E Days of Floral Colours

你怎么写个题面还写同位语从句的啊

首先套路地破环为链 考虑序列上 那么染色的方式可以大致分成四种考虑:

1. $1\ 2\ 1$ 即两端同色 中间那个贺对面同色
2. $1\ 2 \ 1\ 2$ 即两两相邻同色
3. $1\ 1$ 相邻
4. $1$ 和对面同色

考虑 dp:

$$g_n\text{表示长度为}i\text{的序列中只存在}2,3\text{情况的方案数}\\ \text{显然有}g_n=g_{n-2}+g_{n-4}\\ $$

$$f_{0,n}\text{表示}4\text{情况作为首尾有}n\text{个球的方案数}\\ f_{1,n}\text{表示}\frac{2}{3}\text{的}1\text{情况后}4\text{的情况前中间有}n\text{的球的方案数}\\ f_{2,n}\text{表示首尾是}\frac{2}{3}\text{的}1\text{情况中间有}n\text{个球的方案数}\\ \text{显然有}\\ \begin{aligned} f_{0,n}&=g_nn^2+\sum_{i+j=n-1}f_{0,i}g_jj^2+\sum_{i+j=n-3}f_{1,i}g_{j}(j+1)^2\\ f_{1,n}&=g_n(n+1)^2+\sum_{i+j=n-1}f_{0,i}g_j(j+1)^2+\sum_{i+j=n-3}f_{1,i}g_j(j+2)^2\\ f_{2,n}&=g_n(n+2)^2+\sum_{i+j=n-1}f_{1,i}g_j(j+1)^2+\sum_{i+j=n-3}f_{2,i}g_j(j+2)^2\\ ans&=\sum_{i=2}^{n-2}i(i-1)^2(g_{i-1}f_{0,n-i-1}+2g_{i-2}f_{1,n-i-2}+g_{i-3}f_{2,n-i-3}) \end{aligned}$$

把上面那堆全部写成生成函数的形式:

$$\begin{aligned} G(x)&=\sum_{i}g_ix^i=\frac{1}{1-x^2-x^4}\\ G_0(x)&=\sum_{i}g_ii^2x^i\\ G_1(x)&=\sum_{i}g_i(i+1)^2x^i\\ G_2(x)&=\sum_{i}g_i(i+2)^2x^i\\ F_0(x)&=\sum_{i}f_{0,i}x^i\\ F_1(x)&=\sum_{i}f_{1,i}x^i\\ F_2(x)&=\sum_{i}f_{2,i}x^i\\ F_0(x)&=G_0(x)+G_0(x)F_0(x)x+G_1(x)F_1(x)x^3\\ F_1(x)&=G_1(x)+G_1(x)F_0(x)x+G_2(x)F_1(x)x^3\\ F_2(x)&=G_x(x)+G_x(x)F_x(x)x+G_2(x)F_2(x)x^3 \end{aligned}$$
我们跳过解方程 快进到结论:
$$\begin{aligned} F_0(x)&=\frac{G_1(x)x^3-G_0(x)(G_2(x)x^3-1)}{(G_0(x)x-1)(G_2(x)x^3-1)-G^2_1(x)x^4}\\ F_1(x)&=\frac{G_1(x)}{(G_0(x)x-1)(G_2(x)x^3-1)-G_1^2(x)x^4}\\ F_2(x)&=\frac{G_2(x)+G_1(x)F_1(x)x}{1-G_2(x)x^3} \end{aligned}$$
然后我们如何求 $G_0(x),G_1(x),G_2(x)$ 我们有:
$$\begin{aligned} G_0(x)&=G''(x)x^2+G'(x)x\\ G_1(x)&=G''(x)x^2+3G'(x)x+G(x)\\ G_2(x)&=G''(x)x^2+5G'(x)x+4G(x)\\ \end{aligned}$$
然后把 $G(x)$ 带入 得到:
$$\begin{aligned} G_0(x)=\frac{16x^8+12x^6+20x^4+4x^2}{-x^{12}-3x^{10}+5x^6-3x^2+1}\\ G_1(x)=\frac{9x^8+2x^6+23x^4+6x^2+1}{-x^{12}-3x^{10}+5x^6-3x^2+1}\\ G_2(x)=\frac{4x^8-4x^6+24x^4+4x^2+4}{-x^{12}-3x^{10}+5x^6-3x^2+1}\\ \end{aligned}$$
带入 $F_0(x),F_1(x),F_2(x)$ 然后写出最后答案的生成函数 就能得到最后的答案是这个:
$$\frac{24x^3+4x^4+144x^5-4x^6+348x^7-128x^8+240x^9+28x^{10}+188x^{11}-68x^{12}+16x^{13}+4x^{15}}{1-4x^2-8x^3+x^4-16x^5+10x^6-4x^7+12x^8+48x^9-26x^{10}+44x^{11}-15x^{12}+16x^{13}+4x^{14}+4x^{15}+x^{16}}$$
然后分母线性递推就可以了 :)

于是我就偷懒直接 ntt 了

int f[N << 2] = {0,0,0,24,4,144,mod - 4,348,mod - 128,240,28,188,mod - 68,16,0,4,0};
int g[N << 2] = {1,0,mod - 4,mod - 8,1,mod - 16,10,mod - 4,12,48,mod - 26,44,mod - 15,16,4,4,1};
signed main()
{
    read(n);
    n++;
    getinv(g,h,n);
    lim = 1;
    while (lim < (n << 1)) lim <<= 1;
    getr(lim);
    for (int i = n; i < lim; i++)
        f[i] = h[i] = 0;
    ntt(h,1);
    ntt(f,1);
    for (int i = 0; i < lim; i++) h[i] = h[i] * f[i] % mod;
    ntt(h,-1);
    writeln(h[n - 1]);
    return 0;
}

loj2267 「SDOI2017」龙与地下城

u1s1 whk 好玩

题意写的太复杂了 简单来说就是:

给你一个随机数生成器 等概率地生成一个 $[0,X)$ 的整数

你生成 $Y$ 次 问你生成的数的和在 $[a,b]$ 的概率

我们知道一个满足正态分布的随机变量 $\mathcal X(\mu,\sigma^2)$ 的概率密度函数:

$$f(x)=\frac{e^{-\frac{(x-\mu)^2}{\sigma^2}}}{\sqrt{2\pi\sigma^2}}$$
其中 $\mu$ 是期望 $\sigma$ 是标准差

但是题目中的并不是正态分布 由中心极限定理可以知道:

$$\mathcal Y_n=\frac{\sum_{i=1}^n\mathcal X_i-n\mu}{\sqrt{n\sigma^2}}$$
当 $n$ 足够大时可以近似看作正态分布

于是我们事实上就是求

$$\mathcal Y_n\in[\frac{a-n\mu}{\sqrt{n\sigma^2}},\frac{b-n\mu}{\sqrt{n\sigma^2}}]$$
用自带函数 $\operatorname{erf}$ 求就可以了

小数据大力 $\operatorname{dp}$ 就可以了

namespace sub1
{
    double f[N];
    signed main(int x,int y)
    {
        f[0] = pow(1.0 / x,y);
        for (int i = 1; i <= x * y - 1; i++)
        {
            f[i] = 0;
            for (int j = 1; j <= min(x - 1,i); j++)
                f[i] += y * j * f[i - j] - (i - j) * f[i - j];
            f[i] /= i;
        }
        for (int i = 1; i <= x * y - 1; i++)
            f[i] += f[i - 1];
        for (int t = 1; t <= 10; t++)
        {
            int l,r;
            read(l,r);
            printf("%.7lf\n",f[r] - (l ? f[l - 1] : 0));
        }
        return 0;
    }
}
namespace sub2
{
    const double qaq = sqrt(2);
    signed main(int x,int y)
    {
        double mu = (x - 1) / 2.0 * y,sig = sqrt((x * x - 1) / 12.0 * y);
        for (int t = 1; t <= 10; t++)
        {
            int l,r;
            read(l,r);
            printf("%.7lf\n",(erf((r - mu) / sig / qaq) - erf((l - 1 - mu) / sig / qaq)) / 2);
        }
        return 0;
    }
}
signed main()
{
    int t;
    read(t);
    while (t--)
    {
        int x,y;
        read(x,y);
        if (x * y <= 2000) sub1::main(x,y);
        else sub2::main(x,y);
    }
    return 0;
}

AGC035F Two Histograms

考虑什么时候会重复计算方案 当且仅当 $k_i=j-1,l_j=i$ 和 $k_i=j,l_j=i-1$

我们考虑去掉这种方案 我们统计不存在 $k_i=j-1,l_j=i$ 的方案

考虑容斥或者二项式反演 枚举满足上条件的行列数 快进到最后的式子:

$$\sum_{i=0}^{min(n,m)}(-1)^i{n\choose i}{m\choose i}i!(n+1)^{m-i}(m+1)^{n-i}$$
快进到代码:

signed main()
{
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    read(n,m);
    int ans = 0,res = 0;
    for (int i = 0; i <= n && i <= m; i++)
    {
        if (i & 1) ans = (ans - C(n,i) * C(m,i) % mod * fac[i] % mod * ksm(n + 1, m - i) % mod * ksm(m + 1,n - i) % mod + mod) % mod;
        else ans = (ans + C(n,i) * C(m,i) % mod * fac[i] % mod * ksm(n + 1, m - i) % mod * ksm(m + 1,n - i) % mod) % mod;
    }
    writeln(ans);
    return 0;
}

ARC101C Ribbons on Tree

直接考虑容斥 枚举没有被染色的边的数量 考虑把边断开之后的每一棵子树分开染色 一棵大小为 $n$ 的树的方案:

$$f(n)=\prod_{i=1}^{\frac{n}{2}-1}(n-2i)$$
直接树形 dp 就可以了 时间复杂度 $\mathcal O(n^2)$

给个实现:

void dfs(int u,int fa)
{
    siz[u] = dp[u][1] = 1;
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = pnt[i];
        if (v == fa) continue;
        dfs(v,u);
        for (int j = 1; j <= siz[u] + siz[v]; j++) g[j] = 0;
        for (int j = siz[u]; j >= 1; j--)
            for (int k = siz[v]; k >= 0; k--)
                g[j + k] = (g[j + k] + dp[u][j] * dp[v][k] % mod) % mod;
        for (int j = 1; j <= siz[u] + siz[v]; j++) dp[u][j] = g[j];
        siz[u] += siz[v];
    }
    for (int i = 2; i <= siz[u]; i += 2)
        dp[u][0] = (dp[u][0] - dp[u][i] * f[i] % mod + mod) % mod;
}
signed main()
{
    memset(head,-1,sizeof(head));
    read(n);
    for (int i = 1; i < n; i++)
    {
        int u,v;
        read(u,v);
        add_edge(u,v);
        add_edge(v,u);
    }
    f[0] = 1;
    for (int i = 2; i <= n; i += 2)
        f[i] = f[i - 2] * (i - 1) % mod;
    dfs(1,0);
    writeln(mod - dp[1][0]);
    return 0;
}