夏日的雨,就像人间的相遇,来也匆匆,去也匆匆。

微风吹过夏日的树梢,发出阵阵沙沙的响声;白云慵懒地在天空游荡,去往那遥远的天际;飞鸟自由遨游于天地间,在空中完成了一曲华丽的芭蕾舞;阳光慵懒的照在楼宇间,给整个校园镀上了一层安详,这个世界是如此的温柔,唯独对我是如此的冷酷。

当那片阴云笼罩了整个心间,我为不必再追求虚幻飘渺之物而感到欢欣。然而我终明白,这片阴云与我而言是永夜,与他人而言不过是成功前的不平静罢了。

儿时我们盼望着成长,期待着改变,长大后才发现原来一成未变也可以是褒义词。不知是这个世界变化的太快,还是我走的太慢,一转眼,你已不再是当年我认识的那副摸样。

【随笔】日常1

回到文化课已有1周有余……回去以后感觉真的是恍如隔世啊,听说5月就开始一轮复习了,别人复习我预习,真是……不知道说啥好啊。

现在天天过着还算规律的生活,早上6点起,40吃完早饭去学校,到大门口7点,然后一直呆到晚上9点55,中间40min的课我能发上20min的呆,10点左右能出校门口,回去洗洗刷11点半睡觉。周而复始,生生不息?

回去的生活……一个词形容的话,就是麻木,每天像一个机器人一样,按照既定的流程,做着既定的事情,看着既定的试题,接受既定的人生。没有任何的动力,更说不上快乐,与其说是上课,倒更像是熬日子。

前两天和GNAQ在群里聊天的时候谈起文化课,他说,文化课就是拼时间,大家都这么干,你不这么干就没有人管你,同学会远离,老师会忽视。仔细想想,说的很有道理。“高考工厂”,一个曾经感觉很遥远的词,现在却有了很深的体会。整个一中就是一个大工厂,老师就是流水线上的辛勤的工人,而我们就是流水线生产出来的一个个零件,高考过去再经过大学的深加工,最后投入社会这个大机器,成为这个机器上的一个不起眼的零件,或许是螺丝钉,或许是齿轮……而这一台台机器以超设计标准的速度运转,榨干每个人的每一滴血液,只为让那些站在社会顶端的人吃的人血馒头更香甜一点。最后当你老了,被榨干了最后一点价值,光阴的轮转将你的体力消耗殆尽,让你的精力干涸殆尽,他们再把你从自己的位子一脚踹开,最后你在世界的角落里,迎来了自己的终点。

而我和同学的唯一区别,大概就是我是个残次品吧。一个莫得心态的残次品。

现在上课的时候,看着校园里、课本上随处可见的心灵鸡汤,其中英语课本尤甚,这些鸡汤一罐一罐,天天以近乎催眠出现在你的眼前,不停地告诉你要成功,要奋斗。这些鸡汤看的,说句实话,想吐。

昨天,哦不对已经是前天了,前天中午,和基友在学校的人工湖畔聊人生。他跟我讲,他现在总是感觉自己很努力了,比起周围的同学沉沦于安逸的环境,他有着属于自己的理想,并愿意为之不停的奋斗、努力,但无论自己如何努力,自己总是和心里的目标有着差距,自然不免有的时候心生无力。

听到他说这些其实挺有感慨的,因为看到他就好像看到了R1前的自己,那个时候的我又何尝不是不断用一场幻梦麻醉自己呢?只是,风一吹,这个泡泡就破了。

我们每一个人的成长道路上,身边的家长、老师、学校,乃至整个社会环境,都在告诉我们,失败可耻,成功为荣,只要努力就会有回报。但事实上,跟我们说这些的人——他们大多数都谈不上各种意义上的成功,谈哪门子成功学呢?

事实上,大多数人只看到了那些,站在金字塔顶端的人,身披金甲圣衣,脚踏七彩祥云,带着耀眼的光芒,看起来风光无比,却从来没看到,这个金字塔是由一个个败者的遗骸所堆叠起来的,一将功成万骨枯,对于芸芸众生,大多数人终其一生,也只不过是那些成功者脚下的垫脚石罢了。世人皆说努力就会有回报,可事实上,努力是这个世界上门槛最低的事物,每一个人都有条件去做到这两个字,当然愿不愿意是另一回事。比起天赋、机遇,努力,实在是太廉价了。

比起生活中无处不在的“成功学”,现代中国更缺乏对失败的教育,人们总是习惯性的追求成功,可是毕竟金字塔顶端的空间是有限的,从一开始能站上去的人数限制就是固定的,大多数人无论怎么挣扎,其失败的命运就已经注定了。这很残酷,却也很真实。无论你是否赞同,它就存在于此,这不是仅仅说是反抗社会的风气就可以解决的,胜者为王败者寇,这是历史的规律,是永远无解的问题。

我想,比起学会努力,不如先学会怎么样接受现实,怎样面对自己的平庸。学会在这凉薄的人世间,寻一份属于自己的幸福。比起如何成为一个winner,先学会成为生活的loser,难道不是更重要的吗?

而不要像我——梦做多了,已经分不清现实虚幻了。

【luoguP4600】[HEOI2012]旅行问题

这个题……tm是个语文阅读题吧。

翻译成人话就是,现在给定两个串,取他们的前缀,设这两个前缀分别为a,b,要求出一个最长的后缀,且这个后缀一定作为过某个字符串的前缀出现过。

仔细思考下……这tm不是建一个ac自动机然后fail树求lca吗

#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 ms = (1 << 20), mo = 1e9 + 7;

int n, m, la, lb, lc, ld, pos[ms << 1], len[ms], ta, Q[ms];

char s[ms];

struct Acam
{
    int ch[ms][26], ne[ms], de[ms], tot, cnt, head[ms], ha[ms], tp[ms], sz[ms], son[ms], fa[ms];

    inline void insert(int l)
    {
        int no = 0;
        for(ri i = 0; i < l; i ++)
        {
            if(!ch[no][s[i] - 'a'])
                ch[no][s[i] - 'a'] = ++ cnt, ha[ch[no][s[i] - 'a']] = (26ll * ha[no] + s[i] - 'a') % mo;
            no = ch[no][s[i] - 'a'], pos[++ ta] = no;
        }
    }

    inline void init()
    {
        re(n); int Len;
        for(ri i = 1; i <= n; i ++)
            scanf("%s", s), Len = strlen(s), len[i] = len[i - 1] + Len, insert(Len);
    }

    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 dfs1(int no)
    {
        de[no] = (no != 0) ? de[fa[no]] + 1 : 1, sz[no] = 1;
        for(ri i = head[no]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(to == fa[no])
                continue;
            fa[to] = no, dfs1(to), sz[no] += sz[to];
            if((!son[no]) || (sz[son[no]] < sz[to]))
                son[no] = to;
        }
    }

    void dfs2(int no, int t)
    {
        tp[no] = t;
        if(son[no])
            dfs2(son[no], t);
        for(ri i = head[no]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(to == fa[no] || to == son[no])
                continue;
            dfs2(to, to);
        }
    }

    inline int lca(int x, int y)
    {
        while(tp[x] ^ tp[y])
            de[tp[x]] >= de[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];
        return de[x] <= de[y] ? x : y;  
    }

    inline void build()
    {
        memset(head, -1, sizeof(int) * (cnt + 1)), tot = -1;
        int h1 = 0, t1 = -1;
        for(ri i = 0; i < 26; i ++)
            if(ch[0][i])
                Q[++ t1] = ch[0][i];
        while(h1 <= t1)
        {
            int qaq = Q[h1 ++]; Build(qaq, ne[qaq]);
            for(ri i = 0; i < 26; i ++)
            {
                if(ch[qaq][i])
                    ne[ch[qaq][i]] = ch[ne[qaq]][i], Q[++ t1] = ch[qaq][i];
                else
                    ch[qaq][i] = ch[ne[qaq]][i];
            }
        }
        fa[0] = -1, dfs1(0), dfs2(0, 0);
    }
}acam;

int main()
{
    acam.init(), acam.build();
    re(m);
    while(m --)
    {
        re(la), re(lb), re(lc), re(ld);
        int p1 = pos[len[la - 1] + lb], p2 = pos[len[lc - 1] + ld];
        //cout << p1 << ' ' << p2 << ' ' << acam.lca(p1, p2) << '\n';
        printf("%d\n", acam.ha[acam.lca(p1, p2)]);
    }
}

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

【luoguP3792】由乃与大母神原型和偶像崇拜

这个题目……佛了。
有一个一定不会被hack但是我写不出来的做法,考虑离散化+插入中间空位里面不存在的数,这个时候查询区间max,min和后继的min就可以做到一定正确,但是这样会被卡空间……cnbb
然后我们考虑随机化贪心,考虑给每个权值随机一个数,然后查询区间的异或和是否和我们预处理的一样即可。

#include <bits/stdc++.h>
#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 long long ulo;

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 = 5e5 + 10;

int n, m, lx, ly, lz, a[ms], tmpa[ms << 2], ta;

ulo p[ms << 2], su1[ms << 2], su2[ms << 2], P[ms << 2];

mt19937 rnd(time(0));

struct node
{
    int opt, x, y;
}poi[ms];

inline int lowbit(int x)
{
    return x & (-x);
}

inline void change1(int x, ulo v)
{
    while(x <= n)
        su1[x] += v, x += lowbit(x);
}

inline void change2(int x, ulo v)
{
    while(x <= n)
        su2[x] ^= v, x += lowbit(x);
}

inline ulo ask1(int x)
{
    ulo rt = 0;
    while(x)
        rt += su1[x], x -= lowbit(x);
    return rt;
}

inline ulo ask2(int x)
{
    ulo rt = 0;
    while(x)
        rt ^= su2[x], x -= lowbit(x);
    return rt;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(a[i]), tmpa[++ ta] = a[i], tmpa[++ ta] = a[i] + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(lx), re(ly), re(lz), poi[i] = (node){lx, ly, lz};
        if(lx == 1)
            tmpa[++ ta] = lz, tmpa[++ ta] = lz + 1;
    }
    sort(tmpa + 1, tmpa + 1 + ta);
    ta = unique(tmpa + 1, tmpa + 1 + ta) - tmpa - 1;
    p[0] = time(0);
    for(ri i = 1; i <= ta; i ++)
        p[i] = rnd(), P[i] = p[i] ^ P[i - 1];
    for(ri i = 1; i <= n; i ++)
        a[i] = lower_bound(tmpa + 1, tmpa + 1 + ta, a[i]) - tmpa, change1(i, a[i]), change2(i, p[a[i]]);
    for(ri i = 1; i <= m; i ++)
        if(poi[i].opt == 1)
            poi[i].y = lower_bound(tmpa + 1, tmpa + 1 + ta, poi[i].y) - tmpa;
    for(ri i = 1; i <= m; i ++)
    {
        if(poi[i].opt == 1)
            change1(poi[i].x, poi[i].y - a[poi[i].x]), change2(poi[i].x, p[poi[i].y] ^ p[a[poi[i].x]]), a[poi[i].x] = poi[i].y;
        else
        {
            ulo mid; 
            int l, r;
            mid = (ask1(poi[i].y) - ask1(poi[i].x - 1)) / (poi[i].y - poi[i].x + 1);
            l = mid - (poi[i].y - poi[i].x) / 2;
            if ((poi[i].y - poi[i].x) & 1)
                r = mid + (poi[i].y - poi[i].x) / 2 + 1;
            else
                r = mid + (poi[i].y - poi[i].x) / 2;
            if(l <= 0 || r > ta)
                puts("yuanxing");
            else if((ask2(poi[i].y) ^ ask2(poi[i].x - 1)) == (P[r] ^ P[l - 1]))
                puts("damushen");
            else
                puts("yuanxing");
        }
    }
    system("pause");
}

【luoguP4112】[HEOI2015]最短不公共子串

一个序列自动机+后缀自动机的模板好题
首先第一问和第二问就是送分的,枚举a串的起点,将后缀完全插入进两个自动机,看是否能走到一个空节点就行了。
第三问和第四问是一样的,我们设dp_{i,j}表示目前考虑了a串的前i个字符,走到了自动机j号节点的最短子序列长度即可。
然后方程就是
dp_{i,j}=min(dp_{i-1,j},dp_{i-1,from}+1)这样的东西
然后直接在两个自动机上做dp就可以了。可是我傻子不会第三四问

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

const int ms = 4020;

char a[ms], b[ms];

int n, m, dp[2020][ms];

struct Sam
{
    int ch[ms][26], len[ms], fa[ms], las, cnt;

    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];
        if(!las)
            fa[p] = 1;
        else
        {
            int x = ch[las][c];
            if(len[x] == len[las] + 1)
                fa[p] = x;
            else
            {
                int q = ++ cnt; memcpy(ch[q], ch[x], sizeof(ch[x]));
                len[q] = len[las] + 1, fa[q] = fa[x], fa[x] = fa[p] = q;
                while(las && ch[las][c] == x)
                    ch[las][c] = q, las = fa[las];
            }
        }
        las = p;
    }
}sam;

struct Lam
{
    int cnt, ch[ms][26], las[26];

    inline void insert(int c)
    {
        int no = ++ cnt;
        for(ri i = 0; i < 26; i ++)
            ch[no][i] = las[i];
        las[c] = no;
    }

    inline void init()
    {
        for(ri i = 0; i < 26; i ++)
            ch[1][i] = las[i];
    }
}lam;

inline void ask1()
{
    int pri = 1e9 + 7;
    for(ri i = 1, j; i <= n; i ++)
    {
        int no = 1, ci = 0;
        for(j = i; j <= n; j ++)
        {
            ci ++;
            if(!sam.ch[no][a[j] - 'a'])
                break;
            no = sam.ch[no][a[j] - 'a'];
        }
        if(j <= n)
            pri = min(pri, ci);
    }
    if(pri == 1e9 + 7)
        puts("-1");
    else
        printf("%d\n", pri);
}

inline void ask2()
{
    int pri = 1e9 + 7;
    for(ri i = 1, j; i <= n; i ++)
    {
        int no = 1, ci = 0;
        for(j = i; j <= n; j ++)
        {
            ci ++;
            if(!lam.ch[no][a[j] - 'a'])
                break;
            no = lam.ch[no][a[j] - 'a'];
        }
        if(j <= n)
            pri = min(pri, ci);
    }
    if(pri == 1e9 + 7)
        puts("-1");
    else
        printf("%d\n", pri);
}

inline void ask3()
{
    memset(dp, 63, sizeof(dp));
    dp[0][1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        for(ri j = 1; j <= sam.cnt; j ++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        for(ri j = 1; j <= sam.cnt; j ++)
        {
            int to = sam.ch[j][a[i] - 'a'];
            dp[i][to] = min(dp[i][to], min(dp[i - 1][to], dp[i - 1][j] + 1));
        }
    }
    if(dp[n][0] == dp[n + 1][0])
        puts("-1");
    else
        printf("%d\n", dp[n][0]);
}

inline void ask4()
{
    memset(dp, 63, sizeof(dp));
    dp[0][1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        for(ri j = 1; j <= lam.cnt; j ++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        for(ri j = 1; j <= lam.cnt; j ++)
        {
            int to = lam.ch[j][a[i] - 'a'];
            dp[i][to] = min(dp[i][to], min(dp[i - 1][to], dp[i - 1][j] + 1));
        }
    }
    if(dp[n][0] == dp[n + 1][0])
        puts("-1");
    else
        printf("%d\n", dp[n][0]);
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1), m = strlen(b + 1);
    sam.las = 1, sam.cnt = 1, lam.cnt = 1;
    for(ri i = 1; i <= m; i ++)
        sam.insert(b[i] - 'a');
    for(ri i = m; i; i --)
        lam.insert(b[i] - 'a');
    lam.init();
    ask1(), ask2(), ask3(), ask4();
    system("pause");
}

【luoguP4287】[SHOI2011]双倍回文

这是一个PAM的模板题
考虑一个子串成为双倍回文的条件,长度一定为4的倍数,并且沿着fail指针跳一定能跳到一个长度为其二分之一的子串。
那么就建出一个PAM就行,注意有两个根,一个是长度为偶数的回文串,一个是奇数的,找fail指针的时候,之所以是p-len-1,是因为你要考虑从原来p-1出发,往前跳len格正好到对应位置。建法挺像ACAM的。

#include <bits/stdc++.h>
#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;

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 = 5e5 + 10;

char s[ms];

int n, ans;

struct Pam
{
    int ne[ms], f[ms], len[ms], ch[ms][26], tot, las;

    inline int askfail(int x, int p)
    {
        while(s[p] != s[p - len[x] - 1])
            x = ne[x];
        return x;
    }

    inline void insert(int c, int p)
    {
        int no, Fa = askfail(las, p);
        if(!ch[Fa][c])
        {
            ne[no = ++ tot] = ch[askfail(ne[Fa], p)][c];
            len[no] = len[Fa] + 2, ch[Fa][c] = no;
            if(len[ne[no]] <= (len[no] >> 1))
                f[no] = ne[no];
            else
            {
                int P = f[Fa];
                while((len[P] + 2) > (len[no] >> 1) || s[p] != s[p - len[P] - 1])
                    P = ne[P];
                f[no] = ch[P][c];
            }
        }
        las = ch[Fa][c];
    }

    inline void build()
    {
        len[ne[0] = ++ tot] = -1;
        for(ri i = 1; i <= n; i ++)
            insert(s[i] - 'a', i);
    }

    inline void ask()
    {
        for(ri i = 1; i <= tot; i ++)
            if((!(len[i] & 3)) && len[f[i]] == (len[i] >> 1))
                ans = max(ans, len[i]);
    }
}pam;

int main()
{
    re(n), scanf("%s", s + 1);
    pam.build(), pam.ask();
    printf("%d", ans);
    system("pause");
}

【luoguP3239】[HNOI2015]亚瑟王

严重自闭ing
这个题首先一个直接想法是设dp_{i,j}表示目前考虑到第i个人,恰好在第j轮发动技能的概率……然后就发现这样没法转移了,因为一堆概率都是互相关联的,存在后效性。
考虑一个莫得后效性的状态,设dp_{i,j}表示考虑了前i个人,有j个发动技能的代价,那么dp_{i,j}只会和dp_{i-1,j-1},dp_{i-1,j}有关系,这个人单算不发动技能的概率是(1-p_i)^{r-j},相反的,发动技能的概率就是1-(1-p_i)^{r-j}
因此状态转移式子为

dp_{i,j} = dp_{i – 1, j} \cdot (1-p_i)^{r-j} + dp_{i – 1, j – 1} \cdot (1-(1-p_i)^{r-j})

那么对于每个人来说,发动技能的概率就是

P_i = \sum_{j = 0}^{i – 1}dp_{i-1, j} \cdot (1 – (1 – p_i)^{r – j})

最后答案就是

ans = \sum_{i = 1}^n P_i \cdot d_i

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

int T, n, r, d[225];

double dp[225][140], p[225], P[225][225];

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n >> r;
        for(ri i = 1; i <= n; i ++)
            cin >> p[i] >> d[i];
        memset(dp, 0, sizeof(dp)), memset(P, 0, sizeof(P));
        for(ri i = 1; i <= n; i ++)
        {
            P[i][0] = 1;
            for(ri j = 1; j <= r; j ++)
                P[i][j] = P[i][j - 1] * (1 - p[i]);
        }
        dp[0][0] = 1;
        for(ri i = 1; i <= n; i ++)
            for(ri j = 0; j <= min(i, r); j ++)
            {
                dp[i][j] = dp[i - 1][j] * P[i][r - j];
                if(j > 0)
                    dp[i][j] += dp[i - 1][j - 1] * (1 - P[i][r - j + 1]);
            }
        double pri = 0.0;
        for(ri i = 1; i <= n; i ++)
        {
            double tmp = 0.0;
            for(ri j = 0; j < min(i, r); j ++)
                tmp += dp[i - 1][j] * (1 - P[i][r - j]);
            pri += tmp * d[i];
        }
        printf("%.10lf\n", (double)pri);
        //cout << pri << '\n';
    }
}