lxl 的一套神仙题。。

A. Nephren gives a riddle

预处理出前几个串（4\cdot 10^{18} 以内）的串长。一个串可以分为五部分，没有处理到的只会到前两个部分。递归复读即可。

B. Ithea Plays With Chtholly

考虑暴力从一端开始维护序列，即每次找到最前面的不小于 p_i 的位置修改。这样做最坏情况下需要回合数为 nc。

然后发现有些特别大的数一开始就插到左边是不合适的，于是我们将 \leq\frac{c}{2} 的数从左边插入，将 >\frac{c}{2} 的数从右边插入，这样每个数最多只会被修改 \frac{c}{2} 次，就可以通过了。

C. Willem, Chtholly and Seniorious

这个题可以说十分经典了。。Old Driver Tree（ODT，珂朵莉树）的模板题。

原理什么的好像不用说了，复杂度我也不会证，所以直接上板子好了。

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef map<int, ll>::iterator iter;
const int MAXN=110000;
int qpow(int n, int k, int p)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%p;
        n=1ll*n*n%p; k>>=1;
    }
    return r;
}
struct ODT
{
    map<int, ll> s;
    ll find(int p) { return s.lower_bound(p)->second; }
    void split(int p) { ll v=find(p); s[p]=v; }
    pair<iter, iter> range(int l, int r)
    {
        split(l-1), split(r);
        return make_pair(s.find(l-1), s.find(r));
    }
    void build(int* a, int n)
    {
        for (int i=1; i<=n; i++) s[i]=a[i];
    }
    void add(int l, int r, int x)
    {
        iter op, cl; tie(op, cl)=range(l, r);
        while (op!=cl) cl->second+=x, cl--;
    }
    void assign(int l, int r, int x)
    {
        iter op, cl; tie(op, cl)=range(l, r);
        while (op!=cl) s.erase(cl--); s[r]=x;
    }
    ll kth(int l, int r, int x)
    {
        vector<pair<ll, int>> vec; int nxt;
        for (int i=l; i<=r; i=nxt+1)
        {
            iter cur=s.lower_bound(i);
            nxt=min(r, cur->first);
            vec.push_back(make_pair(cur->second, nxt-i+1));
        }
        sort(vec.begin(), vec.end());
        int c=0;
        for (auto p:vec)
            if ((c+=p.second)>=x) return p.first;
        return -1;
    }
    int query(int l, int r, int x, int y)
    {
        ll sum=0; int nxt;
        for (int i=l; i<=r; i=nxt+1)
        {
            iter cur=s.lower_bound(i);
            nxt=min(r, cur->first);
            sum=(sum+1ll*(nxt-i+1)*qpow(cur->second%y, x, y))%y;
        }
        return sum;
    }
} odt;
int n, m, seed, vmax;
int a[MAXN];
int rnd()
{
    int ret=seed;
    seed=(7ll*seed+13)%1000000007;
    return ret;
}
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &seed, &vmax);
    for (int i=1; i<=n; i++) a[i]=rnd()%vmax+1;
    odt.build(a, n);
    for (int i=1; i<=m; i++)
    {
        int op=rnd()%4+1, l=rnd()%n+1, r=rnd()%n+1, x, y;
        if (l>r) swap(l, r);
        if (op==3) x=rnd()%(r-l+1)+1;
        else x=rnd()%vmax+1;
        if (op==4) y=rnd()%vmax+1;
        switch (op)
        {
            case 1: odt.add(l, r, x); break;
            case 2: odt.assign(l, r, x); break;
            case 3: printf("%lld\n", odt.kth(l, r, x)); break;
            case 4: printf("%d\n", odt.query(l, r, x, y)); break;
        }
    }
    return 0;
}

D. Nephren Runs a Cinema

挺不错的一道卡特兰数/组合计数题。

先考虑奈芙莲没有遇到刷卡的观众，且最后 50 元纸币的数量为 0 的情况。可以采用数形结合的思想，问题转化为从 (0,0) 开始，只能往右上或右下走，走到 (n,0) 的方案数。那么方案数是 \binom{n}{\frac{n}{2}}，但需要排除找不开钱的情况，即这条折线不能经过 y=-1。这里有个巧妙的方法处理。

如图，将起点对称到 (-2,0)，那么可以看到每一种不合法（经过 y=-1）的情况都会对应一条从 (-2,0) 开始到 (n,0) 的折线。比如上图中的不合法的红色折线对应着与绿色折线拼合的折线。因此不合法的方案数为 \binom{n}{\frac{n}{2}+1}，答案为 \binom{n}{\frac{n}{2}}-\binom{n}{\frac{n}{2}+1}，实际上就是卡特兰数。现在再考虑最终有 k 张 50 元纸币的方案，实际上就是将终点改为了 (n,k) ，可以同理求出答案为 \binom{n}{\frac{n+k}{2}}-\binom{n}{\frac{n+k}{2}+1}。如果要求一个区间 [l,r] 的答案，将上式求和得

发现其中相邻的两项可以消掉，因此

加入刷卡的情况，其实没有影响，枚举刷卡人数 i 那么其贡献相当于上面问题 n-i 的答案乘上一个 \binom{n}{i} 的系数。即

于是我们的问题就得到了解决？

但这题的模数并不一定是个质数，所以组合数不太好算。lxl 的题解用了扩展卢卡斯，但其实没有必要。因为这里的 n 不大，可以预处理阶乘。具体地，将 p 分解质因数，维护与 p 互质的部分和 p 的每个质因子的幂次即可。互质的部分可以欧拉定理求逆元，幂次可以直接取负。下面是代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef vector<pair<int, int>> PD;
const int MAXN=110000;
const int MAXK=12;
PD get_factor(int n)
{
    PD ret;
    for (int i=2; i*i<=n; i++)
        if (n%i==0)
        {
            int cnt=0;
            while (n%i==0) n/=i, cnt++;
            ret.push_back(make_pair(i, cnt));
        }
    if (n>1) ret.push_back(make_pair(n, 1));
    return ret;
}
int p; PD d;
inline int id(int n)
{
    for (int i=0; i<d.size(); i++)
        if (n==d[i].first) return i;
    return -1;
}
void exgcd(int a, int b, int& x, int& y)
{
    if (b==0) x=1, y=0;
    else exgcd(b, a%b, y, x), y-=a/b*x;
}
inline int inv(int a)
{
    int x, y;
    exgcd(a, p, x, y);
    return (1ll*x%p+p)%p;
}
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%p;
        n=1ll*n*n%p; k>>=1;
    }
    return r;
}
struct Int
{
    int x, a[MAXK];
    Int() {}
    Int(int n)
    {
        x=1; memset(a, 0, sizeof a);
        PD t=get_factor(n);
        for (auto r:t)
        {
            int pos=id(r.first);
            if (~pos) a[pos]=r.second;
            else x=1ll*x*qpow(r.first, r.second)%p;
        }
    }
    int val()
    {
        int ret=x;
        for (int i=0; i<d.size(); i++)
            ret=1ll*ret*qpow(d[i].first, a[i])%p;
        return ret;
    }
    friend Int inv(const Int& num)
    {
        Int ret; ret.x=inv(num.x);
        for (int i=0; i<d.size(); i++) ret.a[i]=-num.a[i];
        return ret;
    }
    friend Int operator * (const Int& lhs, const Int& rhs)
    {
        Int ret; ret.x=1ll*lhs.x*rhs.x%p;
        for (int i=0; i<d.size(); i++)
            ret.a[i]=lhs.a[i]+rhs.a[i];
        return ret;
    }
};
Int fac[MAXN];
int C(int n, int m)
{
    if (m<0||m>n) return 0;
    return (fac[n]*inv(fac[m])*inv(fac[n-m])).val();
}
int calc(int n, int l, int r)
{
    return (1ll*C(n, (n+l+1)/2)-C(n, (n+min(n, r))/2+1)+p)%p;
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n, l, r;
    scanf("%d%d%d%d", &n, &p, &l, &r);
    d=get_factor(p);
    fac[0].x=1;
    for (int i=1; i<=n; i++) fac[i]=fac[i-1]*i;
    int ans=0;
    for (int i=0; i<=n; i++)
        ans=(ans+1ll*C(n, i)*calc(n-i, l, r))%p;
    printf("%d\n", ans);
    return 0;
}