【算法】wqs二分/dp凸优化

wqs二分是去年省选d2t2林特卡特树捧红的。学了一发结果忘得贼tm干净QAQ,还是记一下吧。
思想挺简单的其实,我们会发现有些dp问题他们的答案随着某一维度的上升而具有单调性,然后我们选择每次dp转移的时候减少/增加一定的代价,将这个凸壳拉变形,然后看看最凸的点是在答案左侧还是右侧,之后进行调整
luoguP3620[APIO/CTSC 2007]数据备份
这个题目第一次做的时候我是用堆贪心做的,简直司 马,今天想复习下wqs,学了下发现用wqs贼简单,写了一发吊着捶我的堆贪心。
考虑一个简单的dp
dp_{i,j,0/1}表示目前考虑了前i个人,划了j条线,第i个人有没有划线的最小代价

dp_{i,j,0}=min(dp_{i-1,j,0},dp_{i-1,j,1})\\ dp_{i,j,1}=dp_{i-1,j,0}+s_i-s_{i-1}

现在发现随着j这一维度增加,dp值也在单调递增,而且增速越来越快,感性理解下的话就是开始我们会选取尽可能小的,但是小的被选光了只能选更大的了。
因此我们再设置一个函数h(x) = min(dp_{n,x,0},dp_{n,x,1})
然后二分h(x)-kx中的k,以求出最低点的x,如果x小于题目中给定条数就更新答案,把左边界向右移动,否则把右边界想左移动。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 1e5 + 10;

struct node
{
    lo x, y;

    inline bool operator < (const node &a) const
    {
        return x < a.x;
    }
}dp[ms][2];

int n, m;

lo s[ms], ans;

inline void solve(lo mid)
{
    memset(dp, 63, sizeof(dp)); dp[1][0].x = 0, dp[1][0].y = 0;
    for(ri i = 2; i <= n; i ++)
    {
        dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = (node){dp[i - 1][0].x + s[i] - s[i - 1] - mid, dp[i - 1][0].y + 1};
    }
    dp[n][0] = min(dp[n][0], dp[n][1]);
}

int main()
{
    re(n), re(m);
    lo l = 0, r = 0;
    for(ri i = 1; i <= n; i ++)
        re(s[i]), r += s[i];
    while(l <= r)
    {
        lo mid = (l + r) >> 1; solve(mid);
        if(dp[n][0].y <= m)
            ans = dp[n][0].x + mid * m, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%lld", ans);
}

【luoguP1587】[NOI2016]循环之美

首先最好想的条件,(i, j)=1

第二个条件,设一个无限循环小数的循环节长度为l,那么
i \cdot k^l \equiv i (mod \; j)\\ k^l \equiv 1 (mod \; j)
想一下,i的小数部分都是mod \; j以后的结果,乘上k^l是让小数点整体左移,小数部分不会发生改变

因此我们实际上是求这么一个式子
\sum_{i = 1}^n \sum_{j = 1}^m [(i, j) = 1][(j, k) = 1]
接下来就是数学推导
\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^m [(i, j) = 1][(j, k) = 1] &= \sum_{j = 1}^m \sum_{i = 1}^n [(i, j) = 1][(j, k) = 1]\\ &= \sum_{j = 1}^m [(j, k) = 1] \sum_{i = 1}^n [(i, j) = 1]\\ &= \sum_{j = 1}^m [(j, k) = 1] \sum_{i = 1}^n \sum_{d|i,d|j} \mu(d)\\ &= \sum_{d = 1}^n \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{j = 1}^m [d|j][(j, k) = 1]\\ &= \sum_{d = 1}^n \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}[(jd, k) = 1]\\ &= \sum_{d = 1}^n \mu(d) \lfloor \frac{n}{d} \rfloor [(d, k) = 1] \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}[(j, k) = 1]\\ \end{aligned}
到这一步,我们将式子拆成两半分析,首先考虑简单一点的式子

f(x) = \sum_{j = 1}^x[(j, k) = 1]​

那么对于一个数a \leq k​,如果(a,k)=1​,那么(a+bk, k) = 1​

所以我们有这么一个式子

f(x) = \lfloor \frac{n}{x} \rfloor f(k) + f(x \; mod \; k) ​

第二个式子是S(x,k) = \sum_{d = 1}^n \mu(d) [(d, k) = 1]​
\begin{aligned} S(x,k) &= \sum_{d = 1}^x \mu(d) [(d, k) = 1]\\ &= \sum_{d=1}^x\mu(d) \sum_{D|d,D|k}\mu(D)\\ &= \sum_{D|k}\mu(D) \sum_{D|d}\mu(d)\\ &= \sum_{D|k}\mu(D) \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(dD) \end{aligned}
d, k​不互质的时候,\mu(dD)=0​,并不会有影响,互质的话我们就可以按照积性函数的性质拆开了
\begin{aligned} S(x,k) &= \sum_{D|k}\mu(D) \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(dD)\\ &= \sum_{D|k}\mu(D) \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(d) \cdot \mu(D)\\ &= \sum_{D|k}\mu(D)^2 \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(d)[(d, D) = 1]\\ &= \sum_{D|k}\mu(D)^2 S(\frac{x}{D}, D) \end{aligned}
然后就开始递归杜教筛了
公式要命(确信)

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

lo n, m, K, ans, f[2020], smu[10000010];

bool flag[10000010];

int mu[10000010], prime[1000010], cnt;

inline int gcd(int a, int b)
{
    int c;
    while(b)
        c = a, a = b, b = c % b;
    return a;
}

map <pair<int, int>, int> mmp;

lo asks(lo x, lo y)
{
    if((y == 1 && x <= 10000000) || (!x))
        return smu[x];
    pair <int, int> tm = make_pair(x, y);
    if(mmp[tm])
        return mmp[tm];
    lo rt = 0;
    if(y == 1)
    {
        rt = 1;
        for(ri i = 2, j; i <= x; i = j + 1)//还记得luogu的模板题目吗
            j = x / (x / i), rt -= (j - i + 1) * asks(x / i, 1); 
    }
    else
    {
        for(ri i = 1; i * i <= y; i ++)
            if(y % i == 0)
            {
                if(mu[i])
                    rt += asks(x / i, i);
                if(i * i != y && mu[y / i])
                    rt += asks(x / (y / i), y / i);
            }
    }
    return mmp[tm] = rt;
}

int main()
{
    re(n), re(m), re(K); flag[1] = 1, mu[1] = 1;
    for(ri i = 2; i <= 10000000; i ++)
    {
        if(!flag[i])
            prime[++ cnt] = i, mu[i] = -1;
        ri d;
        for(ri j = 1; j <= cnt && (d = i * prime[j]) <= 10000000; j ++)
        {
            flag[d] = 1;
            if(i % prime[j] == 0)
                break;
            mu[d] = -mu[i];
        }
    }
    for(ri i = 1; i <= K; i ++)
        f[i] = f[i - 1] + (gcd(i, K) == 1);
    for(ri i = 1; i <= 10000000; i ++)
        smu[i] = smu[i - 1] + mu[i];
    lo no = 0, las = 0;
    for(ri i = 1, j; i <= min(n, m); i = j + 1)
    {
        j = min(n / (n / i), m / (m / i));
        no = asks(j, K);
        ans += 1ll * (no - las) * (n / i) * (((m / i) / K) * f[K] + f[(m / i) % K]);
        //cout << i << ' ' << j << ' ' << las << ' ' << no << ' ' << ans << '\n';
        las = no;
    }
    printf("%lld", ans);
}

【算法】杜教筛&二项式反演&莫比乌斯反演

在此之前,狄利克雷卷积
(f·g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})
积性函数嘛……虽然看起来像是完全积性函数……记住就好了。
但是一般我们并不真的直接这么看,我们会想办法把d|n变成\lfloor \frac{n}{d} \rfloor
然后再扯两个比较常见的,狄利克雷卷积结果
\sum_{d|n}\mu(d) = [n=1] = (\mu · 1) = e
\sum_{d|n}\phi(d) = n = (\phi · 1) = id
接下来,开始杜教筛。

杜教筛

假如有一个积性函数f(i),现在我们要求它的前缀和,即\sum_{i=1}^{n}f(i)
杜教筛的目的是,通过将原有的函数卷上别的函数,得到一个比较好算的狄利克雷卷积形式,加速运算。
我们先写一个普通形式

\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d})

然后交换求和顺序,将d提前

\begin{aligned} \sum_{d=1}^{n}g(d)\sum_{d|i}f(\frac{i}{d}) &= \sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i)\\ &= \sum_{d=1}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor) \end{aligned}

这里我把i的含义换成了\frac{i}{d}
那么

g(1)S(n) = \sum_{i=1}^{m}(f·g)(i)-\sum_{d=2}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor)

假如\sum_{i=1}^{m}(f·g)(i)这个式子可以在一个较为快速的时间里面计算,那么我们就可以递归地套数论分块计算\sum_{d=2}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor)这个式子。
假如f(i)=\mu(i),那么根据之前的一个狄利克雷卷积结果

\sum_{d|n}\mu(d) = [n=1] = (\mu · 1) = e

g(i)换成1(i)

\sum_{i=1}^{m}(f·g)(i)=1

这实际上是对于[i=1]求了个前缀和。
所以最后的公式就是

S(n)=1-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)

\mu(i)换成\phi(i),那么利用第二个结论

\sum_{d|n}\phi(d) = n = (\phi · 1) = id

g(i)=1(i)这个不动,但是前面发生了改变

S(n)=\frac{n(n-1)}{2}-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)

杜教筛可以通过处理n较小的部分加速运算,这样做的复杂度大概会到n^{\frac{2}{3}}这样的级别左右。

二项式反演

二项式反演一共有两个形式

f(n) = \sum_{i=0}^{n} (-1)^i C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^i C_n^i f(i)

f(n) = \sum_{i=0}^{n} C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} C_n^i f(i)

只推一下第一个吧

\begin{aligned} g(n) &= \sum_{i=0}^n(-1)^iC_n^i\sum_{j=0}^{i}(-1)^jC_i^jg(j)\\ &= \sum_{j=0}^ng(j)\sum_{i=j}^nC_n^iC_j^i(-1)^{i+j} \end{aligned}

\begin{aligned} g(n) &= \sum_{j=0}^{n}C_n^jg(j)\sum_{i=0}^{n-j}C_{n-j}^{n-i}(-1)^{i+2j}\\ &= \sum_{j=0}^{n}C_n^jg(j)(1-1)^{n-j}\sum_{i=0}^{n-j}C_{n-j}^{n-i}(-1)^{i} \end{aligned}

到这里其实已经很明显了,后面部分是二项式定理的展开,也就说

g(n)=\sum_{j=0}^{n}C_n^jg(j)(1-1)^{n-j}

只有j=n的时候这个式子才不为0,也就说g(n)=g(n),得证。
[BZOJ 2839]集合计数
g(k)表示目前有交集的元素个数为k并且符合条件的方案数,f(k)表示重合元素至少有k个符合条件的方案数。
那么,f(k)=C_n^k(2^{2^{n-k}}-1)
这个2^{2^{n-k}}-1,幂次上的2^{n-k}是考虑固定之后所有的集合,下面的2表示每个集合选不选,这个时候一定要选择一个集合。
但是这样会存在重复的情况,比如你选定了2,3这两个元素被重合,但事实上重合的部分是2,3,4,这个时候就会产生错误的计算了。
因此你要减去k+1个元素被选定的情况,然而你发现k+2的情况被多选择了,因此最后写出来是这样的
g(k)=\sum_{i=k}^{n}(-1)^{i-k}C_i^kf(i)
然后O(n)算就好了……我也不知道为什么qb的老师会放在二项式反演。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo mo = 1000000007;

lo n, k, ans, fac[1000010], inv[1000010];

inline lo ksm(lo x, lo K, lo Mo)
{
    lo rt = 1, a = x;
    while(K)
        rt = rt * ((K & 1) ? a : 1) % Mo, a = a * a % Mo, K >>= 1;
    return rt;
}

int main()
{
    re(n), re(k);
    fac[1] = inv[1] = fac[0] = inv[0] = 1;
    for(ri i = 2; i <= n; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[n] = ksm(fac[n], mo - 2, mo);
    for(ri i = n - 1; i > 1; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = k; i <= n; i ++)
    {
        lo tmp = fac[n] * inv[i] % mo * inv[n - i] % mo * (((ksm(2, ksm(2, (n - i), mo - 1), mo) - 1) % mo + mo) % mo) % mo;
        tmp = tmp * fac[i] % mo * inv[k] % mo * inv[i - k] % mo;
        if((i - k) & 1)
            ans = ((ans - tmp) % mo + mo) % mo;
        else
            ans = (ans + tmp) % mo;
    }
    printf("%lld", ans);
}

【算法】生成函数

推荐博客组合数学之三 —— 生成函数
生成函数是一种解决计数问题的好办法,一般多项式幂次表示方案的样子,系数表示有多少种方式。
比如这个1 1 1 1 1……的数列,就可以表示成f(x) = \sum_{i=0}^{+\infty}x^i
然后首先第一个应用最简单的应用,就是根据这个性质加速背包问题,我们把单个物品的体积看作幂次,然后如果有这种体积的物品就在这次上+1,用fft/ntt进行卷积,可以把一个n变成logn
比如这个题目luoguP3779[SDOI2017]龙与地下城
这个题目就是一个典型,我们要分情况考虑,对于较小的数据,我们可以直接列出一个初始多项式f(x)=\sum_{i=0}^{n-1}\frac{1}{n}x^i
然后我们对于这个多项式进行快速幂,求出它y次方。
那么对大数据的范围呢?
这个东西就要考虑正态分布等一堆东西就是了。
题解 P3779 【[SDOI2017]龙与地下城】
题目里面给你了这个函数的方差和期望公式,而你会发现60分做法和这两个东西毫无关系。他们真正的目的是想让你想到正态分布上面去。
事实上你感性想一下就会知道,这个概率会在中间那段特别大,会画出一个波峰,那个东西就叫做正态分布。
正态分布的密度函数是f(x)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{\frac{-(x-\mu)^2}{2\sigma^2}}
看起来可以用c++自带的exp计算了,但是遗憾的是精度达不到。
但是根据中心极限定理
Y_n=\frac{\sum_{i=1}^{n}x_i-n\mu}{\sqrt{n\sigma^2}}
这个东西当n足够大是服从正态分布N(0,1)的。
也就说f(x)=\frac{1}{\sqrt{2\pi}}e^{\frac{-x^2}{2}}
然后我们就得到了一个可以大力辛普森积分的东西。
辛普森积分这个东西思想挺简单的,我们考虑大力用抛物线拟合它。
抛物线的面积公式是
\frac{(r-l)[f(l)+4f(mid)+f(r)]}{6}
然后你每次计算这个区间拆成两半的答案是不是和不拆基本一样,一样就返回,否则递归。

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef unsigned int uint;

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 8e5 + 10;

const double pi = acos(-1.0);

int lx, ly, T, x, y, pos[ms];

struct node
{
    int a, b;
}poi[20];

struct in
{
    double r, i;
}tmpa[ms], tmpb[ms];

struct Poly
{
    int len;

    in a[ms];
}a, ans;


inline in operator + (in a, in b)
{
    return (in){a.r + b.r, a.i + b.i};
}

inline in operator - (in a, in b)
{
    return (in){a.r - b.r, a.i - b.i};
}

inline in operator * (in a, in b)
{
    return (in){a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r};
}

inline void fft(in *A, int len, int tp)
{
    for(ri i = 1; i < len; i ++)
        if(i < pos[i])
            swap(A[i], A[pos[i]]);
    in la, lb;
    for(ri i = 1; i < len; i <<= 1)
    {
        in wn = (in){cos(pi / i), tp * sin(pi / i)};
        for(ri j = 0; j < len; j += (i << 1))
        {
            in w = (in){1, 0};
            for(ri k = j; k < j + i; k ++)
            {
                la = A[k], lb = w * A[k + i], w = w * wn;
                A[k] = la + lb, A[k + i] = la - lb;
            }
        }
    }
}

inline void Mul(Poly &A, Poly B)
{
    int len = 1, num = 0;
    while(len < A.len + B.len)
        len <<= 1, num ++;
    for(ri i = 0; i < A.len; i ++)
        tmpa[i] = A.a[i];
    for(ri i = A.len; i < len; i ++)
        tmpa[i] = (in){0, 0};
    for(ri i = 0; i < B.len; i ++)
        tmpb[i] = B.a[i];
    for(ri i = B.len; i < len; i ++)
        tmpb[i] = (in){0, 0};
    for(ri i = 1; i < len; i ++)
        pos[i] = ((pos[i >> 1] >> 1) | ((i & 1) << (num - 1)));
    fft(tmpa, len, 1), fft(tmpb, len, 1);
    for(ri i = 0; i < len; i ++)
        tmpa[i] = tmpa[i] * tmpb[i];
    fft(tmpa, len, -1);
    for(ri i = 0; i < len; i ++)
        tmpa[i] = (in){tmpa[i].r / len, 0};
    while(len - 1 >= 0 && tmpa[len - 1].r == 0.0)
        len --;
    A.len = len;
    for(ri i = 0; i < len; i ++)
        A.a[i] = tmpa[i];
}

const double eps = 1.0e-12, K = 1 / sqrt(2 * pi);

/*inline double f(double x) { return K * exp(x * x / -2.0); }  //正态分布的概率密度函数
inline double psp(double l, double r) {
    double mid = (l + r) / 2.0;
    return (r - l) * (f(l) + 4.0 * f(mid) + f(r)) / 6.0;
}
inline double ask(double l, double r)  //然后这是Simpson积分的板子
{
    double mid = (l + r) / 2.0;
    double f1 = psp(l, r);
    double f2 = psp(l, mid) + psp(mid, r);
    double res = (-eps < f1 - f2 && f1 - f2 < eps) ? f1 : ask(l, mid) + ask(mid, r);
    return res;
}*/

inline double f(double x)
{
    return K * exp(x * x / -2.0);
}

inline double calc(double l, double r)
{
    double mid = (l + r) / 2;
    return (r - l) * (f(l) + 4.0 * f(mid) + f(r)) / 6.0;
}

double ask(double l, double r)
{
    double mid = (l + r) / 2;
    double f1 = calc(l, r), f2 = calc(l, mid) + calc(mid, r);
    double rt = (fabs(f1 - f2) < eps) ? f1 : ask(l, mid) + ask(mid, r);
    return rt;  
}

int main()
{
    re(T);
    while(T --)
    {
        re(x), re(y);
        int mx = 0;
        /**/if(x * y <= 524288)
        {
            for(ri i = 1; i <= 10; i ++)
                re(poi[i].a), re(poi[i].b), mx = max(mx, poi[i].b);
            a.len = x;
            double TT = x;
            for(ri i = 0; i < x; i ++)
                a.a[i].r = 1 / TT;
            ans.len = 1, ans.a[0].r = 1;
            int tmpy = y;
            while(tmpy)
            {
                if(tmpy & 1)
                    Mul(ans, a);
                Mul(a, a), tmpy >>= 1;
            }
            for(ri i = 1; i <= 10; i ++)
            {
                double pri = 0;
                for(ri j = poi[i].a; j <= poi[i].b; j ++)
                    pri += ans.a[j].r;
                printf("%.6lf\n", pri);
            }
        }
        else
        {
            double mu = (double)(x - 1) / 2, simga = (double)(x * x - 1) / 12;
            for(ri i = 1; i <= 10; i ++)
            {
                double aa, bb;
                scanf("%lf%lf", &aa, &bb);
                aa = (aa - y * mu) / sqrt(y * simga);
                bb = (bb - y * mu) / sqrt(y * simga);
                //cout << aa << ' ' << bb << '\n';
                printf("%.6lf\n", ask(0, bb) - ask(0, aa));
            }
        }
    }
}

但生成函数的形式还很多样,比如最开始的这个生成函数,我们现在想对它求个通项……至于求通项何用,后面会有例题的。
我们考虑利用高中的等比数列求和知识,错位相减
S_n=\sum_{i=0}^{n}x^i
xS_n=\sum_{i=0}^{n}x^{i+1}
(1-x)S_n=1-x^{n+1}
S_n = \frac{1-x^{n+1}}{1-x}
注意到在生成函数里面,我们并不关心x具体是几,而比较关心它的幂次和系数,所以这个x的大小就任我们所取。
我们考虑当n趋近于无限,x大于0小于1的时候,x^{n+1}可以近似看作0,那么
S_n=\frac{1}{1-x}
其他的,取奇数/偶数/k的倍数其实也是一个道理,只不过有的时候你需要提出一个x而已
我们还需要了解一个东西——负数情况下的二项式定理
(1+x)^{-n}=\sum_{i=0}^{\infty}=(-1)^iC_{n+i-1}^{i}x^i
(1-x)^{-n}=\sum_{i=0}^{\infty}=(-1)^iC_{n+i-1}^{i}(-x)^i=\sum_{i=0}^{\infty}=C_{n+i-1}^{i}x^i
那就上例题吧BZOJ3028食物
这就是我们刚才所写的一个集合
(1+x)^2(1+x+x^2)(1+x+x^2+x^3)(x+x^3+x^5+……)(1+x^4+x^8+……)(1+x^3+x^6+……)=\frac{x}{(1-x)^4}
\frac{x}{(1-x)^4}=\sum_{i=0}^{n}C_{n+3}^3 x^{i+1}
对于x^{n}来说,它的系数就是C_{n+2}^3
考虑卢卡斯,将n分解成kp+x,求C_{x+2}^3就是了

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef unsigned int uint;

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

char s[1010];

const int mo = 10007;

int n, fac[11000], inv[11000];

inline int ksm(int x, int k)
{
    int rt = 1, a = x;
    for(; k; k >>= 1, a = a * a % mo)
        if(k & 1)
            rt = rt * a % mo;
    return rt;
}

int main()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    fac[1] = 1, fac[0] = 1, inv[1] = 1, inv[0] = 1;
    for(ri i = 2; i < mo; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[mo - 1] = ksm(fac[mo - 1], mo - 2);
    for(ri i = mo - 2; i >= 2; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = 1; i <= len; i ++)
        n = (n * 10 + s[i] - '0') % mo;
    printf("%d", fac[(n + 2) % mo] * inv[3] % mo * inv[(n + mo - 1) % mo] % mo);
}

丢个大招luoguP3784[SDOI2017]遗忘的集合
这个题目先考虑S的生成函数,对于S内的某个元素i,其生成函数为[i\in S]\sum_{j=0}^{\infty}x^{ij}=(\frac{1}{1-x^i})^{a_i}
其中a_i=0/1
F(x)=\prod_{i=1}^{\infty}(\frac{1}{1-x^i})^{a_i}
现在我们已知F(x)的系数,想通过它来得到a_i
首先,多项式两边同时取-ln
-ln(F(x))=\sum_{i=1}^{\infty}a_i ln(1-x^i)
考虑对ln(1-x^i)进行先求导再积分(想办法换个形式表达)
ln(1-x^i)=\frac{-ix^{i-1}}{1-x^i}
这个时候我们再把\frac{1}{1-x^i}给还原回去。
-ix^{i-1}\sum_{j=0}^{\infty}x^{ij}=-\sum_{j=0}^{\infty}ix^{i(j+1)-1}
然后再利用高中数学积分回去
-\sum_{j=0}^{\infty}\frac{ix^{i(j+1)}}{i(j+1)}=-\sum_{j=1}^{\infty}\frac{x^{ij}}{j}
将这个结果带入到刚才的式子里面
lnF(x)=\sum_{i=1}^{\infty}a_i\sum_{j=1}^{\infty}\frac{x^{ij}}{j}
然后利用莫反的套路,设T = ij
lnF(x)=\sum_{T=1}^{\infty}x^{ij}\sum_{d|T}a_d\frac{d}{T}
然后f_x=\sum_{d|x}a_d\frac{d}{x}
xf_x=\sum_{d|x}a_x x
如果a_x x>0说明,x在S这个集合中。
然后调和级数的复杂度取算这个系数就行了。但是你要写mtt
loj上疯狂在tle的边缘旋转跳跃。真的考虑去背个新的mtt了。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef unsigned int uint;

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const double pi = acos(-1.0);

const int ms = 1 << 20 | 1, Len = 1 << 19, mo = 32767;

int n, pos[ms];

lo p, F[ms], G[ms], C[ms], D[ms];

inline lo ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    for(; k; k >>= 1, a = a * a % p)
        if(k & 1)
            rt = rt * a % p;
    return rt;
}

struct in
{
    double r, i;

    in(double rr = 0.0, double ii = 0.0)
    {
        r = rr, i = ii;
    }

    inline in conj()
    {
        return (in){r, -i};
    }
}ap[ms], P[ms], Q[ms], f[ms], g[ms], apf[ms], apg[ms];

inline in operator + (in a, in b)
{
    return (in){a.r + b.r, a.i + b.i};
}

inline in operator - (in a, in b)
{
    return (in){a.r - b.r, a.i - b.i};
}

inline in operator * (in a, in b)
{
    return (in){a.r * b.r - a.i * b.i, a.i * b.r + a.r * b.i};
}

inline in operator / (in a, in b)
{
    return (in){(a.r * b.r + a.i * b.i) / (b.r * b.r + b.i * b.i), (a.i * b.r - a.r * b.i) / (b.r * b.r + b.i * b.i)};
}

inline void fft(in *a, lo len, lo tp)
{
    for(ri i = 1; i < len; i ++)
        if(i < pos[i])
            swap(a[i], a[pos[i]]);
    in la, lb;
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = j; k < j + i; k ++)
            {
                in w(cos((k - j) * pi / i), tp * sin((k - j) * pi / i));
                la = a[k], lb = w * a[k + i];
                a[k] = la + lb, a[k + i] = la - lb;
            }
    if(tp == -1)
        for(ri i = 0; i < len; i ++)
            a[i].r /= 1.0 * len, a[i].i /= 1.0 * len;
}

inline void mtt(lo *a, lo *b, lo *c, lo len)
{
    int x = 1, num = 0;
    while(x < len + len)
        x <<= 1, num ++;
    for(ri i = 0; i < len; i ++)
    {
        a[i] %= p, b[i] %= p;
        ap[i] = (in){a[i] & mo, a[i] >> 15}, P[i] = (in){b[i] & mo, b[i] >> 15};
    }
    for(ri i = len; i < x; i ++)
        P[i] = (in){0, 0}, ap[i] = P[i];
    for(ri i = 0; i < x; i ++)
        pos[i] = ((pos[i >> 1] >> 1) | ((i & 1) << (num - 1)));
    fft(ap, x, 1), fft(P, x, 1);
    for(ri i = 0; i < x; i ++)
        Q[i] = P[(x - i) & (x - 1)].conj();
    //in g1(0, 2), g2(2, 0);
    in g1(0, -0.5), g2(0.5, 0);
    for(ri i = 0; i < x; i ++)
        f[i] = (P[i] + Q[i]) * g2, g[i] = (P[i] - Q[i]) * g1;
    for(ri i = 0; i < x; i ++)
        apf[i] = ap[i] * f[i], apg[i] = ap[i] * g[i];
    fft(apf, x, -1), fft(apg, x, -1);
    for(ri i = 0; i < len; i ++)
    {
        lo tmpa = (lo)(apf[i].r + 0.5) % p;
        lo tmpb = (((lo)(apf[i].i + 0.5) % p) << 15) % p;
        lo tmpc = (((lo)(apg[i].r + 0.5) % p) << 15) % p;
        lo tmpd = (((lo)(apg[i].i + 0.5) % p) << 30ll) % p;
        //cout << tmpa << ' ' << tmpb << ' ' << tmpc << ' ' << tmpd << '\n';
        c[i] = (tmpa + tmpb + tmpc + tmpd) % p;
    }
    for(ri i = len; i < x; i ++)
        c[i] = 0;
}

void merge(lo *A, lo *B, lo len)
{
    if(len == 1)
    {
        A[0] = ksm(B[0], p - 2); return;
    }
    merge(A, B, (len + 1) >> 1);
    mtt(A, B, C, len), mtt(A, C, D, len);
    for(ri i = 0; i < len; i ++)
        A[i] = (A[i] + A[i]) % p;
    for(ri i = 0; i < len; i ++)
        A[i] = ((A[i] - D[i]) % p + p) % p;
}

inline void askln(lo *A, lo n, lo *B)
{
    lo tmp[ms], inv[ms];
    for(ri i = 1; i <= n; i ++)
        tmp[i - 1] = A[i] * i % p;
    memset(inv, 0, sizeof(inv));
    merge(inv, A, n + 1);
    mtt(inv, tmp, B, n);
    //for(ri i = 0; i <= n; i ++)
    //  cout << B[i] << ' ';
    //cout << '\n';
    for(ri i = n; i; i --)
        B[i] = B[i - 1] * ksm(i, p - 2) % p;
}

int main()
{
    re(n), re(p), F[0] = 1;
    memset(G, 0, sizeof(G));
    for(ri i = 1; i <= n; re(F[i ++]));
    askln(F, n, G);
    for(ri i = 1; i <= n; i ++)
        G[i] = G[i] * i % p;
    for(ri i = 1; i <= n; i ++)
        for(ri j = (i << 1); j <= n; j += i)
            G[j] += p - G[i], G[j] -= (G[j] >= p) ? p : 0;
    int ans = 0;
    for(ri i = 1; i <= n; i ++)
        if(G[i])
            ans ++;
    printf("%d\n", ans);
    for(ri i = 1; i <= n; i ++)
        if(G[i])
            printf("%d ", i);
}

【luoguP4094】[HEOI2016/TJOI2016]字符串

学艺不精学艺不精,sa&sam都是一瓶子不满半瓶子咣当,自闭了。
现在我们要求公共前缀,对sam来说,前缀不好求但后缀好求,翻转整个串,这样就变成公共后缀了,并且这个后缀满足,对于s[b-len+1,a],存在一个结束点和s[d,c]在同一个endpos集合里面并且长度长度至少为len。那么就倒序建一个sam,然后模拟建出后缀树(常见套路),并用线段树合并来维护endpos。
询问的时候二分答案,并且从c所在位置沿着后缀树往上面跳,跳到长度不小于二分值的最上方。然后线段树查询即可。
看不透sa的解法,突然发现自己不懂为什么height维护的是sa_i却可以做原串的lcp,自闭。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef unsigned int uint;

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 1e5 + 10; 

int n, m, tmpsz[ms << 1], poi[ms << 1], pos[ms];

char s[ms];

struct Sam
{
    int ch[ms << 1][26], len[ms << 1], cnt, las, Root[ms << 1], fa[ms << 1][21];

    struct Seg
    {
        int ch[ms << 6][2], su[ms << 6], tot;

        void insert(int &w, int l, int r, int ll)
        {
            if(!w)
                w = ++ tot;
            if(l == r)
            {
                su[w] ++; return;
            }
            int mid = (l + r) >> 1;
            if(ll <= mid)
                insert(ch[w][0], l, mid, ll);
            else
                insert(ch[w][1], mid + 1, r, ll);
            su[w] = su[ch[w][0]] + su[ch[w][1]];
        }

        int merge(int x, int y, int l, int r)
        {
            if((!x) || (!y))
                return x + y;
            if(l == r)
            {
                su[x] += su[y]; return x;
            }
            int mid = (l + r) >> 1, rt = ++ tot;
            ch[rt][0] = merge(ch[x][0], ch[y][0], l, mid), ch[rt][1] = merge(ch[x][1], ch[y][1], mid + 1, r);
            su[rt] = su[ch[rt][0]] + su[ch[rt][1]];
            return rt;
        }

        int ask(int w, int l, int r, int ll, int rr)
        {
            if(!w)
                return 0;
            if(l == ll && r == rr)
                return su[w];
            int mid = (l + r) >> 1;
            if(rr <= mid)
                return ask(ch[w][0], l, mid, ll, rr);
            else if(ll > mid)
                return ask(ch[w][1], mid + 1, r, ll, rr);
            return ask(ch[w][0], l, mid, ll, mid) + ask(ch[w][1], mid + 1, r, mid + 1, rr);
        }
    }seg;

    inline void insert(int c)
    {
        int p = ++ cnt; len[p] = len[las] + 1;
        while(las && (!ch[las][c]))
            ch[las][c] = p, las = fa[las][0];
        if(!las)
            fa[p][0] = 1;
        else
        {
            int x = ch[las][c];
            if(len[x] == len[las] + 1)
                fa[p][0] = x;
            else
            {
                int q = ++ cnt; len[q] = len[las] + 1, fa[q][0] = fa[x][0];
                memcpy(ch[q], ch[x], sizeof(ch[q])), fa[x][0] = q, fa[p][0] = q;
                while(las && ch[las][c] == x)
                    ch[las][c] = q, las = fa[las][0];
            }
        }
        las = p;
    }

    inline void build()
    {
        cnt = 1, las = 1;
        reverse(s + 1, s + 1 + n);
        for(ri i = 1; i <= n; i ++)
            insert(s[i] - 'a'), seg.insert(Root[las], 1, n, i), pos[i] = las;
        for(ri i = 1; i <= cnt; i ++)
            tmpsz[len[i]] ++;
        for(ri i = 1; i <= n; i ++)
            tmpsz[i] += tmpsz[i - 1];
        for(ri i = 1; i <= cnt; i ++)
            poi[tmpsz[len[i]] --] = i;
        for(ri i = 1; i <= 20; i ++)
            for(ri j = 1; j <= cnt; j ++)
                fa[j][i] = fa[fa[j][i - 1]][i - 1];
        for(ri i = cnt; i; i --)
            if(fa[poi[i]][0])
                Root[fa[poi[i]][0]] = seg.merge(Root[fa[poi[i]][0]], Root[poi[i]], 1, n);
    }

    inline bool check(int Len, int p, int l, int r)
    {
        for(ri i = 20; ~i; i --)
            if(len[fa[p][i]] >= Len && fa[p][i])
                p = fa[p][i];
        //cout << p << '\n';
        return seg.ask(Root[p], 1, n, l + Len - 1, r);
    }

    inline void solve()
    {
        int a, b, c, d;
        while(m --)
        {
            re(a), re(b), re(c), re(d);
            a = n + 1 - a, b = n + 1 - b, c = n + 1 - c, d = n + 1 - d;
            int l = 0, r = min(a - b + 1, c - d + 1), ans = 0;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(check(mid, pos[c], b, a))
                    ans = mid, l = mid + 1;
                else
                    r = mid - 1;
            }   
            printf("%d\n", ans);
        }
    }
}sam;

int main()
{
    re(n), re(m);
    scanf("%s", s + 1);
    sam.build(), sam.solve();
}

【luoguP3920】[WC2014]紫荆花之恋

n m d, w s m,劳资就是头铁,过了233333333333333333333
这个破题简直司马。
首先这个式子很好变化
Dis_{i}表示目前i这个点到根的距离。
Dis_{i}+Dis_{j}-2Dis_{lca(i,j)} \leq r_{i} + r_{j}
那么
Dis_{i} – r_{i}-Dis_{lca(i,j)} \leq r_{j} – Dis_{j} + Dis_{lca(i,j)}
然后你就直接把每个点都当lca来看的话,把左右两边的值插进u这个点的平衡树就好了,注意因为你要查询它的父亲,所以要把子树的信息传上来,建两个平衡树,这是因为假如你到达了lca的父亲,思考下,如果直接查询子树信息,这里会计算deep[lca]次。再外面套个点分树,复杂度O(nlog^2n)
说着挺简单的,维护贼·t·m·恶·心。
首先你的平衡树就不能写splay/fhq,因为这俩哥们太慢。
treap不会,那么剩下最好写的就是替罪羊了。
替罪羊之前扯过。
那么就算你第一层替罪羊写完了,接下来的点分树还是动态的。
那么第二个好像也需要平衡,所以再套一层替罪羊树。可是问题是,如果我们只对点分树的一部分进行重构了,怎么办?
记录每个点在自己父亲儿子中的顺序,每次修改的时候找出Root,然后直接按照它在父亲的顺序进行O(1)的修改。
剩下的细节代码里有,不再详细叙述,大概破了学oi以来写的最长的正解(数据分治暴力不算)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10, Ms = 1e7 + 10;

const double Alpha = 0.8;

int n, lx, ly, lz;

lo lastans;

struct Dt
{
    struct Tree//树本身
    {
        int de[ms], fa[ms], dis[ms][105], sz[ms];

        unsigned h[ms];

        vector <int> a[ms];
    }tre;

    struct edge
    {
        int to, co;
    };

    vector <edge> a[ms];

    int n, cnt, Root, r[ms], w[ms], sz[ms];

    bool flag[ms];

    struct Sgt
    {
        int val[Ms], ch[Ms][2], sz[Ms], sonroot[ms], faroot[ms], Top, mem[Ms], tot, tmp[ms];

        void init(int tot)
        {
            Top = 0;
            for(ri i = tot; i; i --)
                mem[++ Top] = i;
        }

        int newnode(int v)
        {
            int t = mem[Top --]; val[t] = v, sz[t] = 1, ch[t][0] = 0, ch[t][1] = 0;
            return t;
        }

        void dfs(int pos)//准备拍扁重建
        {
            mem[++ Top] = pos;
            if(ch[pos][0])
                dfs(ch[pos][0]);
            tmp[++ tot] = val[pos];//这里是为了严格按照中序遍历
            if(ch[pos][1])
                dfs(ch[pos][1]);
        }

        int rebuild(int l, int r)
        {
            if(l == r)
                return newnode(tmp[l]);
            int mid = (l + r) >> 1, rt = newnode(tmp[mid]);
            sz[rt] = r - l + 1;
            if(mid > l)
                ch[rt][0] = rebuild(l, mid - 1);
            if(mid < r)
                ch[rt][1] = rebuild(mid + 1, r);
            return rt;
        }

        inline int Rebuild(int Rt, int v)//拍扁重建
        {
            tot = 0, dfs(Rt); bool fl = 1;
            for(ri i = 1; i <= tot; i ++)
                if(tmp[i] >= v)
                {
                    tot ++;
                    for(ri j = tot; j > i; j --)
                        tmp[j] = tmp[j - 1];
                    tmp[i] = v, fl = 0; break;
                }
            if(fl)
                tmp[++ tot] = v;
            return rebuild(1, tot);
        }

        void insert(int &x, int v)//替罪羊的重建过程
        {
            if(!x)
            {
                x = newnode(v); return;
            }
            sz[x] ++;
            if(v < val[x])
            {
                if(sz[ch[x][0]] > sz[x] * Alpha)
                    x = Rebuild(x, v);
                else
                    insert(ch[x][0], v);
            }
            else
            {
                if(sz[ch[x][1]] > sz[x] * Alpha)
                    x = Rebuild(x, v);
                else
                    insert(ch[x][1], v);
            }
        }

        void restore(int x)
        {
            mem[++ Top] = x;
            if(ch[x][0])
                restore(ch[x][0]);
            if(ch[x][1])
                restore(ch[x][1]);
        }

        int ask(int x, int v)
        {
            if(x == 0)
                return 0;
            if(v < val[x])
                return ask(ch[x][0], v);
            return ask(ch[x][1], v) + sz[ch[x][0]] + 1;
        }

        void faclear(int x)
        {
            if(faroot[x])
                restore(faroot[x]);
            faroot[x] = 0;
        }

        void sonclear(int x)
        {
            if(sonroot[x])
                restore(sonroot[x]);
            sonroot[x] = 0;
        }

        void fainsert(int x, int v)
        {
            insert(faroot[x], v);
        }

        void soninsert(int x, int v)
        {
            insert(sonroot[x], v);
        }

        int faask(int x, int v)
        {
            return ask(faroot[x], v);
        }

        int sonask(int x, int v)
        {
            return ask(sonroot[x], v);
        }

        void Give(int f, int t)
        {
            sonroot[t] = sonroot[f], sonroot[f] = 0;
        }
    }sgt;

    void init(int x, int y)
    {
        tre.a[0].push_back(0), tre.de[1] = 1, n = x, r[1] = y; 
        w[0] = n + 1, sgt.init(Ms - 1), sgt.fainsert(1, -y);
    }

    void dfs(int x)
    {
        cnt ++; flag[x] = 1; int Si = tre.a[x].size();
        for(ri i = 0; i < Si; i ++)
            dfs(tre.a[x][i]);
    }

    void askroot(int no, int f, int S)
    {
        sz[no] = 1, w[no] = 0; int to, Si = a[no].size();
        for(ri i = 0; i < Si; i ++)
            if((to = a[no][i].to) != f && flag[to])
                askroot(to, no, S), sz[no] += sz[to], w[no] = max(w[no], sz[to]);
        w[no] = max(w[no], S - sz[no]);
        if(w[no] < w[Root])
            Root = no;
    }

    void reasksz(int no, int f)//重新计算size
    {
        sz[no] = 1; int to, Si = a[no].size();
        for(ri i = 0; i < Si; i ++)
            if((to = a[no][i].to) != f && flag[to])
                reasksz(to, no), sz[no] += sz[to];
    }

    void reask(int no, int f, int fr, int d, int c)
    {
        int to;
        tre.sz[fr] ++, tre.dis[no][d] = c;
        sgt.fainsert(fr, c - r[no]), sgt.soninsert(Root, c - r[no]);
        for(ri i = 0; i < a[no].size(); i ++)
            if((to = a[no][i].to) != f && flag[to])
                reask(to, no, fr, d, c + a[no][i].co);
    }

    void Work(int no, int d, int tot)//具体的重构过程
    {
        tre.a[no].clear(), flag[no] = 0, tre.de[no] = d, sgt.faclear(no);
        sgt.fainsert(no, -r[no]), reasksz(no, 0), tre.sz[no] = 1, tre.dis[no][d] = 0;
        int Si = a[no].size(), to, ci = 0;
        for(ri i = 0; i < Si; i ++)
            if(flag[to = a[no][i].to])
                Root = 0, askroot(to, 0, sz[to]), sgt.sonclear(Root), reask(to, no, no, d, a[no][i].co);
        for(ri i = 0; i < Si; i ++)
            if(flag[to = a[no][i].to])//记录所有点在自己点分树上父亲,儿子的顺序
                Root = 0, askroot(to, 0, sz[to]), tre.fa[Root] = no, tre.a[no].push_back(Root), tre.h[Root] = ci, ci ++, Work(Root, d + 1, sz[to]);
    }

    void rebuild(int no)//对最大的不合法的点分树进行重构
    {
        cnt = 0, dfs(no), Root = 0, askroot(no, 0, cnt);
        tre.a[tre.fa[no]][tre.h[no]] = Root, tre.fa[Root] = tre.fa[no];//通过记录原来这个点儿子所在位置,对于没修改的点分树进行快速的对儿子的维护
        sgt.Give(no, Root), Work(Root, tre.de[no], cnt);
    }

    int insert(int no, int x, int y, int z)//插入到真实的树上
    {
        a[no].push_back((edge){x, y}), a[x].push_back((edge){no, y}); 
        r[no] = z, tre.sz[no] = 1, tre.fa[no] = x, tre.de[no] = tre.de[x] + 1;
        tre.a[x].push_back(no), tre.h[no] = tre.a[x].size() - 1;//h记录在父亲的位置?
        tre.dis[no][tre.de[no]] = 0, sgt.fainsert(no, -z);//这个dis应该是利用的随机树高不会超过logn……看脸看脸
        int No = no, las = no, rt = 0;
        for(ri i = tre.de[no] - 1; i; i --)
        {
            las = No, No = tre.fa[No], tre.sz[No] ++;
            tre.dis[no][i] = tre.dis[x][i] + y;//就直接复制点分树的距离
            sgt.fainsert(No, tre.dis[no][i] - z), sgt.soninsert(las, tre.dis[no][i] - z);
            if(tre.sz[las] > tre.sz[No] * Alpha + 1)
                rt = No;
        }
        if(rt)
            rebuild(rt);
        int ans = sgt.faask(no, z) - 1;
        No = no, las = no;
        for(ri i = tre.de[no] - 1; i; i --)
            las = No, No = tre.fa[No], ans += sgt.faask(No, z - tre.dis[no][i]), ans -= sgt.sonask(las, z - tre.dis[no][i]);
        return ans;
    }
}dt;

int main()
{
    re(n), re(n), re(lx), re(ly), re(lz), dt.init(n, lz);
    puts("0");
    for(ri i = 2; i <= n; i ++)
        re(lx), re(ly), re(lz), lx ^= (lastans % 1000000000), lastans += dt.insert(i, lx, ly, lz), printf("%lld\n", lastans);
}

【AGC026】Manju Game

这个题我想了一晚上才民白。
设编号为奇数的盒子为黑色,偶数为白色
我们首先要按照奇偶性讨论,n为偶数的时候,这个时候,先手能去到的一定不会低于max(w, b)w是白色的和,b是黑色,后手一定不会低于min(a,b),因此两个人互相牵制,答案就是这两个数。
考虑奇数的情况,首先先手的答案不会低于b,考虑每次我取黑色点的时候,将问题拆分成两半,一半直接选了,留下另一半递归处理,把这个递归树画出来,你会发现所有的节点都是黑色的,也就说这些段落都是先手拿黑后手拿白,只有一个段落是先手拿白后手拿黑的。二分答案=w+x,二分这个x=w_{l,r}-b_{l,r}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, bla, whi, a[300030];

inline bool check(int v)
{
    int su = 0;
    for(ri i = 1; i <= n; i += 2)
        if(su >= v)
            su = max(su + a[i] - a[i - 1], a[i]);
        else
            su += a[i] - a[i - 1];
    return su >= v;
}

int main()
{
    re(n);
    for(ri i = 1; i <= n; re(a[i]), bla += (i & 1) ? a[i] : 0, whi += (!(i & 1)) ? a[i] : 0, i ++);
    if(!(n & 1))
        printf("%d %d", max(bla, whi), min(bla, whi));
    else
    {
        int l = 0, r = bla, ans = 0;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid))
                ans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d %d", max(bla, whi + ans), min(whi, bla - ans));
    }
}

【AT2307】Tree Game

这个题居然还算今天讲的简单的,我觉得我今年SDOI凉了啊qwq
考虑这么一个事情,对于一个点x和他的子树,这个点先手必胜,一定存在一个儿子son,使得a_{x}>a_{son}并且son这个子树先手必败。
假如a_{x} \leq a_{son},那么后手就可以通过不停回到x然后耗死先手,而a_{x}>a_{son}时候,后手如果跳回x则会被耗死,所以他只能往son这个子树跳,进入这个子树,先后手交换,原来的后手变成了先手,这个时候先手必败,也就说原来的后手必败。
边界条件是跳到叶子节点,这个时候没有任何一个点可以供这个点上的先手跳,为先手必败态。
每次考虑一个点的时候dfs一遍 ,时间复杂度O(n^2)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

bool sta[5050];

int tot = -1, lx, ly, head[5050], n, a[5050];

struct in
{
    int to, ne;
}ter[10010];

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

void dfs(int no, int f)
{
    sta[no] = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == f)
            continue;
        dfs(to, no);
        if(a[no] > a[to] && (!sta[to]))
        {
            sta[no] = 1; break;
        }
    }
}

int main()
{
    re(n), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; re(a[i ++]));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), build(lx, ly);
    for(ri i = 1; i <= n; i ++)
    {
        dfs(i, 0);
        if(sta[i])
            printf("%d ", i);
    }
    system("pause");
}

【CF566E】Restoring Map

这个题只要记住,确定非叶子节点就不停枚举两个点,看他们的neith集合是不是只有两个交点,这两个交点之间连边。剩下的细节代码里有。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

struct edge
{
    int x, y;
}e[1010];

int n, lx, ly, lz, ta;

const int ms = 1024;

bitset <ms> neith[ms], mo[ms], mmp[ms], tmp, flag, vis, leaf;

inline int ask(bitset <ms> a)//查询最低位的1
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        (a & mo[mid]).any() ? r = mid : l = mid + 1;
    }
    return l;
}

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        mo[i] = mo[i - 1], mo[i].set(i);//让i这一位变成1
    for(ri i = 1; i <= n; i ++)
    {
        mmp[i].set(i), re(lx);
        for(ri j = 1; j <= lx; j ++)
            re(ly), neith[i].set(ly);
    }
    for(ri i = 1; i <= n; i ++)
        for(ri j = i + 1; j <= n; j ++)
            if((tmp = (neith[i] & neith[j])).count() == 2)
            {
                lx = ask(tmp), tmp.reset(lx), ly = ask(tmp);//reset是删除这一位的1
                if(!mmp[lx][ly])
                    flag[lx] = flag[ly] = mmp[lx][ly] = mmp[ly][lx] = vis[lx] = vis[ly] = 1, e[++ ta] = (edge){lx, ly};
            }
    if(vis.none())
        for(ri i = 2; i <= n; i ++)
            printf("1 %d\n", i);
    else
    {
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= n; j ++)
                if((tmp = (neith[i] & neith[j])) == neith[i] && tmp != neith[j])
                    leaf.set(j);//判断儿子
        for(ri i = 1; i <= n; i ++)
            if(!leaf[i])
            {
                lx = ask(neith[i] ^ (vis & neith[i]));//找出编号最小的没用过的叶子节点
                vis[lx] = 1, tmp = flag & neith[i];
                if(tmp.count() == 2)//如果只有i和另外一个点,也就说剩下的与i联通的都是叶子
                {
                    ly = ask(tmp), tmp.reset(ly), lz = ask(tmp);
                    if(mmp[ly].count() == 2 && mmp[lz].count() == 2)//如果这俩点目前连出去的边都就一条,剩下的点都是叶子
                    {
                        tmp = neith[i] ^ (neith[i] & flag);//找出与自己直接连接的那些叶子
                        for(ri j = 1; j <= n; j ++)
                            if(j != ly && j != lz)
                                if(tmp[j])
                                    printf("%d %d\n", ly, j);
                                else
                                    printf("%d %d\n", lz, j);
                        printf("%d %d\n", ly, lz);
                        return 0;
                    }
                    else
                        e[++ ta] = (edge){mmp[ly].count() == 2 ? ly : lz, lx};//2是靠叶子的一段
                }
                else
                {
                    while(tmp.any())
                    {
                        ly = ask(tmp);
                        if(mmp[ly] == (flag & neith[i]))//如果i能到达的非叶子节点和ly一样
                        {
                            e[++ ta] = (edge){lx, ly}; break;
                        }
                        tmp.reset(ly);
                    }
                }
            }
        for(ri i = 1; i <= ta; i ++)
            printf("%d %d\n", e[i].x, e[i].y);
    }
    system("pause");
}

【luoguP4221】[WC2018]州区划分

这个题目比较考察科技啊。

首先让我们考虑最暴力的状态方程,设dp_{s}表示目前所有已经被选择的城市集合为s,这样的满意度之和。那么方程为
dp_{s}=\frac{1}{sum_s}\sum_{T\in s}dp_{T}sum_{s-T}

之所以乘\sum_{s-T}是为了抵消原来的分母的影响。这里默认sum都是p次方之后的。

那么现在这个东西首先可以枚举子集来做,复杂度O(3^n),t到不知道哪里去了,接下来怎么办?

注意到后面这个式子,实际上他相当于满足T \; and \; (s-T) = 0,T \; or \; (s-T) = s

那么这个东西就相当Ts-T二进制上的1加起来正好等于s上的1个数,且T \; xor \; (s-T) = s这么一个情况,那么我们多加一维限制,分层fwt。

注意sum就不要逆变换回去了,并且dp值除了最后都要保证一直fwt,正变换之后和fft结果类似,可以O(n)乘起来,还要注意fwt不要带乘法,能换成加减就别用乘法和取模,这破题卡常

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 23;

const int mo = 998244353, inv2 = 499122177;

int lx, fa[ms], ly, n, m, p, de[ms];

int w[ms], su[3000030], dp[ms][3000030], vx[ms][3000030];

struct edge
{
    int x, y;
}e[1010];

inline int ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return (int)rt;
}

inline int ask(int x)
{
    int rt = 0;
    while(x)
        x -= (x & (-x)), rt ++;
    return rt;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool check(int s)
{
    for(ri i = 1; i <= n; i ++)
        fa[i] = i, de[i] = 0;
    int cnt = ask(s), fx, fy;
    for(ri i = 1; i <= m; i ++)
        if(((1 << (e[i].x - 1) & s)) && (((1 << (e[i].y - 1)) & s)))
        {
            de[e[i].x] ++, de[e[i].y] ++, fx = find(e[i].x), fy = find(e[i].y);
            if(fx != fy)
                fa[fx] = fy, cnt --;
        }
    if(cnt > 1)
        return 1;
    for(ri i = 1; i <= n; i ++)
        if(((1 << (i - 1)) & s) && (de[i] & 1))
            return 1;
    return 0;
}

inline int add(int x, int y)
{
    x += y, x -= (x >= mo) ? mo : 0;
    return x;
}

inline void fwt(int *a, int len, int tp)
{
    /*int la, lb;
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = j; k < j + i; k ++)
            {
                la = a[k], lb = a[k + i];
                a[k] = add(la, lb), a[k + i] = add(la, mo - lb);
                if(tp == -1)
                    a[k] = 1ll * a[k] * inv2 % mo, a[k + i] = 1ll * a[k + i] * inv2 % mo;
            }*/
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = 0; k < i; k ++)
                a[j + k + i] = add(a[j + k + i], (tp == -1 ? mo - a[j + k] : a[j + k]));
}

int main()
{
    re(n), re(m), re(p);
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), e[i] = (edge){lx, ly};
    for(ri i = 1; i <= n; i ++)
        re(w[i]);
    int S = 1 << n;
    for(ri s = 0; s < S; s ++)
    {
        int cnt = 0;
        for(ri i = 0; i < n; i ++)
            if((1 << i) & s)
                cnt ++, su[s] += w[i + 1];
        su[s] = ksm(su[s], p), vx[cnt][s] = check(s) ? su[s] : 0;
    }
    dp[0][0] = 1, fwt(dp[0], S, 1);
    for(ri i = 1; i <= n; i ++)
    {
        fwt(vx[i], S, 1);
        for(ri j = 0; j < i; j ++)
            for(ri s = 0; s < S; s ++)
                dp[i][s] = (dp[i][s] + 1ll * dp[j][s] * vx[i - j][s] % mo) % mo;
        fwt(dp[i], S, -1);
        for(ri s = 0; s < S; s ++)
            dp[i][s] = (ask(s) != i) ? 0 : 1ll * dp[i][s] * ksm(su[s], mo - 2) % mo;
        if(i != n)
            fwt(dp[i], S, 1);
    }
    printf("%d", dp[n][S - 1]);
    system("pause");
}