【算法】生成函数

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

【CF618F】Double Knapsack

这个题目甚是神仙啊QAQ。
假设a数组算到最后总和比b大,我们现在考虑对于每一个i,找出最大的ta满足sa_i>=sb_{ta},其中saa数组的前缀和,sbb数组的前缀和。
这个不等式可以写成0 \leq sa_i – sb_{ta} < n,因为只要大于等于n我们就可以继续向前移动ta
我们从0开始统计这个sa_i – sb_{ta} 的值,那么根据鸽巢原理,一共n+1个数字分配在n个笼子里,至少有两对是相等的,也就说不存在无解的情况。

#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 n, lx;

lo sa[ms], sb[ms];

struct in
{
    int x, y;
}pos[ms];

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(sa[i]), sa[i] += sa[i - 1];
    for(ri i = 1; i <= n; i ++)
        re(sb[i]), sb[i] += sb[i - 1];
    for(ri i = 0; i <= n; i ++)
        pos[i] = (in){-1, -1};
    bool f = 0;
    if(sa[n] < sb[n])
        swap(sa, sb), f = 1;
    ri i, ta = 0; lo v;
    for(i = 0; i <= n; i ++)
    {
        while(sa[i] >= sb[ta + 1] && ta + 1 <= n)
            ta ++;
        v = sa[i] - sb[ta];
        //cout << i << ' ' << ta << ' ' << v << '\n';
        if(pos[v].x == -1)
            pos[v] = (in){i, ta};
        else
            break;
    }
    if(f)
        swap(sa, sb), swap(i, ta), swap(pos[v].x, pos[v].y);
    printf("%d\n", i - pos[v].x);
    for(ri j = pos[v].x + 1; j <= i; j ++)
        printf("%d ", j);
    printf("\n");
    printf("%d\n", ta - pos[v].y);
    for(ri j = pos[v].y + 1; j <= ta; j ++)
        printf("%d ", j);
    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");
}