【CF528D】Fuzzy Search

第一次做这种多项式搞字符串的题目,写一下吧

a_i = [s_i 能与 c 匹配],b_i = [t_i = c]
然后对于s串从第i位开始和t串匹配来说

f_i = \sum_{j=0}^{m-1}a_{i+j}b_{j}

这样没法卷积了,因此我们将字符串翻转成m-j-1,然后就变成了可以卷记的形式。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#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;
}

const int mo = 998244353;

const int ms = 5e5 + 10;

int n, m, K, len, a[ms << 2], b[ms << 2], pos[ms << 2], po[ms << 2], inv[ms << 2], cnt[ms << 2];

char s1[ms], s2[ms];

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

inline void ntt(int *a, int len, int tp)
{
    for(ri i = 1; i < len; i ++)
        if(i < pos[i])
            swap(a[i], a[pos[i]]);
    int la, lb, w, wn;
    for(ri i = 1; i < len; i <<= 1)
    {
        wn = (tp == 1) ? po[i] : inv[i];
        for(ri j = 0; j < len; j += (i << 1))
        {
            w = 1;
            for(ri k = j; k < j + i; k ++)
            {
                la = a[k], lb = 1ll * w * a[k + i] % mo, w = 1ll * w * wn % mo;
                a[k] = la + lb, a[k + i] = la - lb, a[k] -= (a[k] >= mo) ? mo : 0, a[k + i] += (a[k + i] < 0) ? mo : 0;
            }
        }
    }
    if(tp == -1)
    {
        int invlen = ksm(len, mo - 2);
        for(ri i = 0; i < len; i ++)
            a[i] = 1ll * a[i] * invlen % mo;
    }
}

inline void solve(char c)
{
    int las = -1e9 + 7;
    memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
    for(ri i = 0; i < n; i ++)
    {
        if(s1[i] == c)
            las = i;
        if(i - las <= K)
            a[i] = 1;
    }
    las = 1e9 + 7;
    for(ri i = n - 1; i >= 0; i --)
    {
        if(s1[i] == c)
            las = i;
        if(las - i <= K)
            a[i] = 1;
    }
    for(ri i = 0; i < m; i ++)
        if(s2[i] == c)
            b[i] = 1;
    reverse(b, b + m);
    ntt(a, len, 1), ntt(b, len, 1);
    for(ri i = 0; i < len; i ++)
        a[i] = 1ll * a[i] * b[i] % mo;
    ntt(a, len, -1);
    for(ri i = 0; i < len; i ++)
        cnt[i] += a[i];
}

int main()
{
    re(n), re(m), re(K);
    len = 1; int num = 0;
    while(len < ((n + m) << 1))
        len <<= 1, num ++;
    for(ri i = 1; i < len; i ++)
        pos[i] = ((pos[i >> 1] >> 1) | ((i & 1) << (num - 1)));
    for(ri i = 1; i <= len; i <<= 1)
        po[i] = ksm(3, ((mo - 1) / (i << 1)));
    int inv3 = ksm(3, mo - 2);
    for(ri i = 1; i <= len; i <<= 1)
        inv[i] = ksm(inv3, ((mo - 1) / (i << 1)));
    scanf("%s%s", s1, s2);
    for(ri i = 0; i < 4; i ++)
        solve("ACGT"[i]);
    int pri = 0;
    for(ri i = 0; i < n + m - 1; i ++)
        pri += cnt[i] == m;
    printf("%d", pri);
}

【算法】excrt&exlucas

其实这俩我早就会过,当时还是个傻子不会写数学公式,结果昨晚复习发现自己想不起来怎么做了,然后就滚过来复习下

\begin{cases} x \equiv a_1 (mod \; m_1)\\ x \equiv a_2 (mod \; m_2)\\ x \equiv a_3 (mod \; m_3)\\ ……\\ x \equiv a_n (mod \; m_n)\\ \end{cases}

现在m之间两两不互质,求这个方程组的一组解

假设我们已经求出前i-1组方程的一组解x,设M = lcm(m_1, m_2, m_3, ……, m_{i-1})

那么x+kM是前i-1个方程的通解

那么现在我们就求

x+kM \equiv a_i (mod \; m_i)

然后这个东西就可以通过n次exgcd求出来了。

然后记一个小扩展

假如我们目前知道一个方程

ax \equiv b (mod \; c)

这个东西乍一看不符合excrt的初始条件,但我们可以通过变换形式来构造初始方程

首先我们可以很轻松的用一次exgcd求出这个方程的一组解x_i

然后就有这么一个通解形式

x = x_i + k\frac{c}{(a,b)}

那么我们把这个式子放在mod \; \frac{c}{(a,b)}进行

那么就得到了

x \equiv x_i (mod \; \frac{c}{(a,b)})

这就变成了符合excrt的形式

现在我们要求C_n^m (mod \; P),并且P不是质数

首先质因数分解,P = \prod_{i}p_i^{k_i}

因此我们需要分别计算C_n^m (mod \; p_i^{k_i}),并利用excrt合并即可

现在重点是怎么计算组合数

拆成\frac{n!}{m!(n-m)!}

之后考虑计算阶乘及其逆元

首先对于p的倍数,先把他们拿出来,计算(\lfloor \frac{n}{p} \rfloor)!对于剩下的,不会超过p^k就会有一个循环节

luoguP2183[国家集训队]礼物

首先一眼可以得出式子

C_n^{w_1}C_{n-w_1}^{w_2}……C_{w_n}^{w_n}

这就是个扩展卢卡斯的式子,直接算就是了,代码挺不好写的就是了

#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 P, prime[220], ta, n, m, w[20], ci[220], c[220], pri[220];

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

inline lo mul(lo a, lo b, lo mo)
{
    lo rt = ((long double)a / mo * b + 1.0e-8);
    rt = a * b - rt * mo;
    return rt < 0 ? rt + mo : rt;
}

void exgcd(lo a, lo b, lo &x, lo &y)
{
    if(b == 0)
    {
        x = 1, y = 0; return;
    }
    exgcd(b, a % b, x, y);
    lo p = x, q = y;
    x = y, y = p - a / b * q;
}

inline lo gcd(lo a, lo b)
{
    lo C;
    while(b)
        C = a, a = b, b = C % b;
    return a;
}

inline lo inv(lo a, lo mo)
{
    lo lx, ly; exgcd(a, mo, lx, ly); return (lx % mo + mo) % mo;
}

inline lo askc(lo x, lo y, lo mo)
{
    if(y > x)
        return 0;
    lo rt = 1, a, b;
    for(ri i = 1; i <= y; i ++)
        a = (x - i + 1) % mo, b = inv(i % mo, mo), rt = rt * a % mo * b % mo;
    return rt;
}

lo lucas(lo x, lo y, lo mo)
{
    if(y == 0)
        return 1;
    return askc(x % mo, y % mo, mo) * lucas(x / mo, y / mo, mo) % mo;
}

lo fac(lo x, lo a, lo mo)
{
    if(x == 0)
        return 1;
    lo la = 1, rt;
    for(ri i = 1; i <= mo; i ++)
        if(i % a)
            la = la * i % mo;
    rt = ksm(la, x / mo, mo);
    for(ri i = x / mo * mo + 1; i <= x; i ++)
        if(i % a)
            rt = rt * i % mo;
    return rt * fac(x / a, a, mo) % mo;
}

inline lo exlucas(lo x, lo y, lo a, lo mo)
{
    lo t1, t2, t3, s = 0, tmp;
    for(ri i = x; i > 0; i /= a)
        s += i / a;
    for(ri i = y; i > 0; i /= a)
        s -= i / a;
    for(ri i = x - y; i > 0; i /= a)
        s -= i / a;
    tmp = ksm(a, s, mo), t1 = fac(x, a, mo), t2 = fac(y, a, mo), t3 = fac(x - y, a, mo);
    return tmp * t1 % mo * inv(t2, mo) % mo * inv(t3, mo) % mo;
}

inline lo calc(lo x, lo y)
{
    for(ri i = 1; i <= ta; i ++)
        c[i] = (ci[i] == 1) ? lucas(x, y, prime[i]) : exlucas(x, y, prime[i], pri[i]);  
    lo rt = c[1], M = pri[1];
    for(ri i = 2; i <= ta; i ++)
    {
        lo lx, ly, lz = (c[i] - rt) % pri[i]; lz += (rt < 0) ? pri[i] : 0;
        exgcd(M, pri[i], lx, ly), lx = lx * lz % pri[i];
        rt += lx * M, M = M * pri[i] / gcd(M, pri[i]), rt = (rt + M) % M;
    }
    return rt;
}

int main()
{
    re(P), re(n), re(m);
    lo tmps = 0;
    for(ri i = 1; i <= m; i ++)
        re(w[i]), tmps += w[i];
    if(tmps > n)
    {
        puts("Impossible");
        return 0;
    }
    tmps = P;
    for(ri i = 2; i * i <= tmps; i ++)
        if(tmps % i == 0)
        {
            prime[++ ta] = i, pri[ta] = 1;
            while(tmps % i == 0)
                ci[ta] ++, tmps /= i, pri[ta] *= i;
        }
    if(tmps > 1)
        prime[++ ta] = tmps, ci[ta] = 1, pri[ta] = tmps;
    lo las = 1;
    for(ri i = 1; i <= m; i ++)
        tmps = calc(n, w[i]), n -= w[i], las = las * tmps % P;// cout << las << '\n';
    printf("%lld\n", las);
}

【算法】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);
}

【算法】生成函数

推荐博客组合数学之三 —— 生成函数
生成函数是一种解决计数问题的好办法,一般多项式幂次表示方案的样子,系数表示有多少种方式。
比如这个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);
}

【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);
}

【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");
}

【CF209C】Trails and Glades

题目本身挺简单的,就是正常的构造欧拉回路就是了,还不需要输出方案,简单的一批,唯一需要的是,那些没有边并且单独一个的点是不需要联通他们的,仔细思考下,人家要的是欧拉回路,不是一个所有点都联通的欧拉回路。细节写在代码里。

#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 = 1e6 + 10;

int tot = -1, lx, ly, cnt, ans, head[ms], has, ji, n, m, du[ms];

bool flag[ms], vis[ms];

struct in
{
    int to, ne;
}ter[ms << 1];

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)
{
    flag[no] = 1, ji |= (du[no] & 1);
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(!flag[to])
            dfs(to);
    }
}

int main()
{
    re(n), re(m), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= m; i ++)
    {
        re(lx), re(ly), vis[lx] = 1, vis[ly] = 1;
        if(lx == ly)//自环可以直接不考虑了,只要记录这个点有没有边就行了
            continue; 
        build(lx, ly), du[lx] ++, du[ly] ++;
    }
    vis[1] = 1;
    for(ri i = 1; i <= n; i ++)
    {
        if(du[i] & 1)//度数为奇数,存在另一个点与他相连接
            ans ++, has = 1;
        if((!flag[i]) && vis[i])//如果这里有边并且没被走过
        {
            cnt ++, ji = 0, dfs(i);
            if(!ji)//如果这个联通块没有偶数条边,则要增加重边(对于对面也是)
                ans += 2;
        }
    }
    if(cnt == 1 && has == 0)//如果只有一个联通块并且本来就存在欧拉回路
        ans -= 2;
    printf("%d", ans >> 1);//因为所有操作是对称的,所以直接/2没啥问题
    system("pause");
}

【CF487C】Prefix Product Sequence

构造题都是脑洞嘤嘤嘤。
首先考虑什么时候有解,答案是当n为4或者是质数的时候,之所以4有解是因为,4只能被分解成4=2·2,其他的合数都可以被分解成两个比他小的因数,那么这样在mod \; n意义下就是0了,所以不可能。
那么继续考虑,1不能放在除了第一个地方以外的其他地方,因为放在其他的地方就会出现前缀积相等的情况,n只能放在最后,因为前缀积加入n以后在mod \; n意义下就是0了。
至于中间那些数,我们考虑放入\frac{2}{1},\frac{3}{2},\frac{4}{3}……这样的,显然他们统一减去1以后也不会在mod \; n意义下相等,并且这样的前缀积因为不停抵消实际上就是2,3,4,5……,并不会重复。

#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;
}

lo n;

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

int main()
{
    re(n);
    if(n == 4)
        printf("YES\n1\n3\n2\n4");
    else
    {
        bool f = 1;
        for(ri i = 2; i * i <= n; i ++)
            if(n % i == 0)
            {
                f = 0; break;
            }
        if(!f)
            printf("NO");
        else
        {
            puts("YES");
            printf("1\n");
            for(ri i = 2; i < n; i ++)
                printf("%lld\n", (lo)i * ksm(i - 1, n - 2, n) % n);
            if(n > 1)
                printf("%lld", n);
        }
    }
    system("pause");
}

【CF226D】The table

这个题有一个很显然的贪心想法,每次扫描到某一行或者某一列的时候如果发现和为负数就进行修改。这样的复杂度和正确性是对的,因为显然对于整个表格,你的总权值和是在不断增加的,除了这一行/列以外,其他的点是没有变化的,每次至少增加2,而点权绝对值只有100以内。
注意你还得输出修改次数最小的方案,对于某一行/列,如果修改了偶数次,那么它就是废操作

#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, m, a[110][110], ta1, ta2, sta1[10010], sta2[10010], cnt1[110], cnt2[110];

inline bool check()
{
    for(ri i = 1; i <= n; i ++)
    {
        int su = 0;
        for(ri j = 1; j <= m; j ++)
            su += a[i][j];
        if(su < 0)
            return 1;
    }
    for(ri i = 1; i <= m; i ++)
    {
        int su = 0;
        for(ri j = 1; j <= n; j ++)
            su += a[j][i];
        if(su < 0)
            return 1;
    }
    return 0;
}

inline void print()
{
    for(ri i = 1; i <= n; i ++, printf("\n"))
        for(ri j = 1; j <= m; j ++)
            printf("%d ", a[i][j]);
    printf("\n");
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            re(a[i][j]);
    while(check())
    {
        for(ri i = 1; i <= n; i ++)
        {
            int su = 0;
            for(ri j = 1; j <= m; j ++)
                su += a[i][j];
            if(su < 0)
            {
                for(ri j = 1; j <= m; j ++)
                    a[i][j] = -a[i][j];
                cnt1[i] ++;
                //print();
            }
        }
        for(ri i = 1; i <= m; i ++)
        {
            int su = 0;
            for(ri j = 1; j <= n; j ++)
                su += a[j][i];
            if(su < 0)
            {
                cnt2[i] ++;
                for(ri j = 1; j <= n; j ++)
                    a[j][i] = -a[j][i];
                //print();
            }
        }
    }
    for(ri i = 1; i <= n; i ++)
        if(cnt1[i] & 1)
            sta1[++ ta1] = i;
    for(ri i = 1; i <= m; i ++)
        if(cnt2[i] & 1)
            sta2[++ ta2] = i;
    printf("%d ", ta1);
    for(ri i = 1; i <= ta1; i ++)
        printf("%d ", sta1[i]);
    printf("\n");
    printf("%d ", ta2);
    for(ri i = 1; i <= ta2; i ++)
        printf("%d ", sta2[i]);
    system("pause");
}