Logo kal0rona的博客

博客

「FZOI」OI 寒假赛 #12 Div.1 - 题解

2020-02-25 17:38:00 By kal0rona

A - 幼儿园

这道题的来源是 CF Div.2 D,只有 20 多个人过了。我在比赛的时候差点把这题写出来,然后因为一些玄学错误彻底 GG。

无疑,这是正常比赛中最难的题。但是这道题并不难想:我们可以把多个线段的端点提取出来,然后做一次「线段剖分」。如下图所示:

线段剖分

由于 $m \leq 10^9$,所以我们我们可以离散化之后进行剖分。接下来就是状压 DP 的部分了。由于全部放置之后并不会超过 $k \leq 8$,所以我们可以枚举线段,从上一条线段的覆盖状态进行转移。

线段剖分的具体实现可以用类似差分的方法:给每个位置开一个 Vector,剖分的时候可以在离散化之后的 $[L_i, R_i]$ 上,给 $L_i$ 位置插一个 pair(i, 1),给 $R_i + 1$ 的位置插一个 pair(i, -1)。剖分之后做前缀和即可。

剖分做完了之后,我们就可以进行状态压缩。我们把每个位置中存好的线段 vector 叫做 segover[]。我们枚举到从 $i$ 开始,那么范围用离散化数组表示就是 $[vec[i], vec[i + 1])$。我们把线段上方覆盖的线段进行标号,再用一个 map 维护上一根线段上方覆盖的线段的标号。这里如果我们要知道某条线段在上一个区间中的编号就可以用 map 很快维护了。之后,枚举一个 preStat,也就是上一个区间的覆盖情况。如果 preStat 要求我们选一根这两个区间上方都存在的线段,那么就把其加入「必选」集合中;如果 preStat 中并没有选某根两个区间上方都存在的线段,那么就把其加入「必不选」集合中。最后,把这个必不选集合取反,得到本区间状态的全集。我们可以枚举这个全集的子集,同时保证包含「必选」集合,我们便可以进行转移了。

代码有点复杂,搞清楚了就不难了:

// std.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

typedef pair<int, int> pii;

int n, m, limit, dp[MAX_N][(1 << 8)];
vector<int> vec;
pii segs[MAX_N];
vector<pii> overlay[MAX_N];
vector<int> segover[MAX_N];
set<pii> st;

int ripe(int x) { return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1; }

int getlen(int x) { return segs[x].second - segs[x].first; }

int main()
{
    scanf("%d%d%d", &n, &m, &limit);
    // input;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &segs[i].first, &segs[i].second);
        vec.push_back(segs[i].first);
        vec.push_back(segs[i].second + 1);
        st.insert(segs[i]);
    }
    // make elements and segments unique;
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    int seg_siz = vec.size();
    set<pii>::iterator it = st.begin();
    n = st.size();
    for (int i = 1; i <= n; i++)
        segs[i] = *it, it++;
    // make the diff;
    for (int i = 1; i <= n; i++)
    {
        int l = ripe(segs[i].first), r = ripe(segs[i].second + 1);
        overlay[l].push_back(make_pair(i, 1));
        overlay[r].push_back(make_pair(i, -1));
    }
    // make the sum;
    for (int i = 1; i <= seg_siz; i++)
    {
        segover[i] = segover[i - 1];
        for (auto pr : overlay[i])
            if (pr.second == -1)
            {
                for (vector<int>::iterator it = segover[i].begin(); it != segover[i].end(); it++)
                    if (*it == pr.first)
                    {
                        segover[i].erase(it);
                        break;
                    }
            }
            else
                segover[i].push_back(pr.first);
    }
    // start to dp;
    int ans = 0;
    for (int i = 1; i < seg_siz; i++)
    {
        unordered_map<int, int> idx;
        // rearrange;
        for (int j = 0, siz = segover[i].size(); j < siz; j++)
            idx[segover[i][j]] = j;
        // enumerating the previous stat;
        int pre_siz = segover[i - 1].size();
        for (int pre_stat = 0; pre_stat < (1 << pre_siz); pre_stat++)
        {
            int current_stat = (1 << segover[i].size()) - 1;
            int compulsory = 0;
            // convert the previous id in current id system;
            for (int j = 0; j < pre_siz; j++)
                if (((~pre_stat) & (1 << j)) && idx.count(segover[i - 1][j]))
                    current_stat ^= (1 << idx[segover[i - 1][j]]);
                else if ((pre_stat & (1 << j) && idx.count(segover[i - 1][j])))
                    compulsory ^= (1 << idx[segover[i - 1][j]]);
            // enumerate the subset;
            for (int stat = current_stat;; stat = (stat - 1) & current_stat)
                if ((stat & compulsory) == compulsory)
                {
                    int const_term = vec[i] - vec[i - 1];
                    dp[i][stat] = max(dp[i - 1][pre_stat] + const_term * (__builtin_popcount(stat) & 1), dp[i][stat]);
                    if (i == seg_siz - 1)
                        ans = max(ans, dp[i][stat]);
                    if (stat == 0)
                        break;
                }
                else if (stat == 0)
                    break;
        }
    }
    // output;
    printf("%d\n", ans);
    return 0;
}

B - 床单上的矩阵

这道题比较简单,就是把按位考虑和单调栈混在一起做而已。

我们按位考虑:假设当前我们要算 $2^b$ 的答案,我们可以把这个矩阵变成一个 01 矩阵。我们如果要算 AND,其实就是要算出有多少个子矩阵中不包含 0;要算出 OR,其实就是要算出有多少个子矩阵包括至少一个 0。

那么,我们可以先来枚举一个矩阵的右下角 $(i, j)$。以下面这个矩阵为例:

0 1 1 0 1
0 0 1 1 1
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0

先来算 AND。欲算出多少个子矩阵不包含 0,我们不妨先枚举一个 $i$,在第 $i$ 行的视角来进行检视。假设 $i = 3$ 时,枚举到 $j = 5$。我们可以把可以作为左上角的点给独立出来:

0 0 0 0 1
0 0 1 1 1
1 1 1 1 1

发现其实这个左上角的合法范围就是前 $j$ 个、高度不下降的竖直长方体所组成的一段面积。这就跟单调栈有关了,算一下就完事了。

那么,如果我们要算 OR,算所有至少包含一个 0 的矩阵:其实可以做个容斥,用所有子矩阵个数减去不包含 0 的矩阵个数。不包含 0 的矩阵个数跟上面差不多,随便做做就完事了。

// std.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010, mod = 1e9 + 7;

int n, mat[32][MAX_N][MAX_N], ans1, ans2, tmp[32][MAX_N][MAX_N], stk[MAX_N], wi[MAX_N];

inline char gc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = gc();
    return f * x;
}

int main()
{
    n = read();

    for (int i = 1; i <= n; i++)
        for (int j = 1, val; j <= n; j++)
        {
            val = read();
            for (int b = 0; b <= 30; b++)
                mat[b][i][j] = (val >> b) & 1;
        }
    int submat = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            submat = (0LL + submat + 1LL * i * j % mod) % mod;
    // or;
    for (int b = 0; b <= 30; b++)
    {
        int acc = 0;
        for (int i = 1; i <= n; i++)
        {
            int tail = 0, S = 0;
            for (int j = 1; j <= n; j++)
            {
                if (mat[b][i][j] == 1)
                    tmp[b][i][j] = 0;
                else
                    tmp[b][i][j] = 1 + tmp[b][i - 1][j];
                int w = 0;
                while (tail && tmp[b][i][j] < stk[tail])
                    S = (0LL + S + mod - 1LL * wi[tail] * stk[tail] % mod) % mod, w += wi[tail], tail--;
                w++, stk[++tail] = tmp[b][i][j], wi[tail] = w, S = (0LL + S + 1LL * w * stk[tail] % mod) % mod;
                acc = (0LL + acc + S) % mod;
            }
        }
        ans2 = (0LL + ans2 + 1LL * (0LL + submat + mod - acc) % mod * (1 << b) % mod) % mod;
    }
    for (int b = 0; b <= 30; b++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                mat[b][i][j] = 1 - mat[b][i][j];
    memset(tmp, 0, sizeof(tmp));
    for (int b = 0; b <= 30; b++)
    {
        int acc = 0;
        for (int i = 1; i <= n; i++)
        {
            int tail = 0, S = 0;
            for (int j = 1; j <= n; j++)
            {
                if (mat[b][i][j] == 1)
                    tmp[b][i][j] = 0;
                else
                    tmp[b][i][j] = 1 + tmp[b][i - 1][j];
                int w = 0;
                while (tail && tmp[b][i][j] < stk[tail])
                    S = (0LL + S + mod - 1LL * wi[tail] * stk[tail] % mod) % mod, w += wi[tail], tail--;
                w++, stk[++tail] = tmp[b][i][j], wi[tail] = w, S = (0LL + S + 1LL * w * stk[tail] % mod) % mod;
                acc = (0LL + acc + S) % mod;
            }
        }
        ans1 = (0LL + ans1 + 1LL * acc % mod * (1 << b) % mod) % mod;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

C - 集合幸运数

调和级数进行枚举,然后记录上一个取的位置即可。

// std.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int m, n, last[MAX_N];
vector<long long> ansBox;
bool tag[MAX_N], vis[MAX_N];

int main()
{
    scanf("%d", &m);
    for (int i = 1, val; i <= m; i++)
        scanf("%d", &val), tag[val] = true;
    long long idx = 0;
    scanf("%d", &n);
    for (int i = 1, val, cnt; i <= n; i++)
    {
        scanf("%d", &val), cnt = 0;
        for (int j = last[val] + val; j < MAX_N && cnt < val; last[val] = j, j += val)
            if (!vis[j])
            {
                vis[j] = true, cnt++;
                if (tag[j])
                    ansBox.push_back(cnt + idx);
            }
        idx += val;
    }
    printf("%lld\n", ansBox.size());
    for (int i = 0, siz = ansBox.size(); i < siz; i++)
        printf("%lld\n", ansBox[i]);
    return 0;
}

FZOI WC 2020 抢救计划

2020-01-20 14:05:50 By kal0rona

为了抢救各位被文化课耽误的信息学,kal0rona 出了一套抢救计划。

科技

数据结构

  1. 主席树
  2. 树链剖分
  3. 线段树的各种骚操作
  4. 分块
  5. 左偏树

图论

  1. 虚树
  2. 图连通性 Tarjan
  3. 网络流
  4. 点分治

数学

  1. gcd, lcm, Euler's function.
  2. 线性筛,数论函数
  3. 莫比乌斯反演
  4. 计数问题
  5. 高斯消元

离线

  1. CDQ 分治
  2. 整体二分

计算几何

  1. 扫描线
  2. 凸包

DP

  1. 概率期望 DP
  2. 矩阵快速幂优化

字符串

  1. AC 自动机
  2. Manacher

题单

Codeforces

CF1288D

CF1182E

CF1223D

CF1223C

CF1286C1

CF1264C

CF1168A

CF1009E

AtCoder

AtCoder Grand Contest 002E

AtCoder Grand Contest 001E

LibreOJ

LOJ6029

Universial OJ

UOJ228

Quest OJ

QOJ2030

QOJ2033

QOJ2044

QOJ2017

Sphere OJ

SP3267

Luogu

P4774

P2469

P4099

P2513

P2606

P4284

P2455

P3389

P4103

P3261

P4178

P2495

P3041

P2617

P3242

P3121

「FZOI」OI 寒假赛 #1 Div.1 - 题解

2020-01-17 11:41:56 By kal0rona

A - 资本家 kal0rona

我们可以考虑把每个员工的前缀收益放在折线图上进行考虑:一条折线从$(1, 0)$出发,在$(x, y)$向上走就是给第$x$个员工发钱,上升高度就是发钱数量。最后,把老板当作第$n + 1$个员工即可。可以发现,因为这个是前缀收益,所以最后我们会走到$(n + 1, m)$,我们只需要算从$(1, 0)$到$(n + 1, m)$的不降路径数即可,也就是${n + m \choose m}$。

对于前 40% 的分我们只需要暴力处理组合数即可,用递推式:${n \choose k} = {n - 1 \choose k} + {n - 1 \choose k - 1}$即可。那么对于前 60% 的分我们需要用 Lucas 定理进行处理,也就是: $$ {n \choose k} \bmod p = {\lfloor \frac{n}{p} \rfloor \choose \lfloor \frac{k}{p} \rfloor} \cdot {n \bmod p \choose k \bmod p} \bmod p $$ 发现 $p$ 很小,我们就可以直接处理 $p$ 以内的阶乘和逆元即可计算。

那么对于 80% 的分数,我们可以对不同的模数做两次,然后用 CRT 进行合并即可。那么对于全部分数,就需要一点技巧。我们仍然使用 CRT 进行合并,但是对于每一个质数幂来说计算方式有变化:

我们发现质数幂不能用正常的 Fermat Little Therom 来算,因为有些数字是没有逆元的。在模$p^c$意义下,如果$\gcd(x, p^c) \neq 1$,那么这样的$x$是没有逆元的。那我们如何来计算呢?首先,我们先把组合数写出来: $$ {n \choose k} \bmod p^c = \frac{n!}{(n - k)!k!} \bmod p^c = p^x \frac{f(n!)}{f[(n - k)!]f(k!)} \bmod p^c $$ 其中,我们可以把阶乘中的$p$的幂给提取出来,然后进行上下化简。对于分母,由于与$p$互质,所以可以直接用扩展欧几里得算法得出逆元。至于$p^x$,可以直接快速幂。然后上下式可以直接用类似 Lucas 定理的方式处理(在模意义下,阶乘是有循环率的,自己打个表康康即可)即可。处理时需要记录$p$的出现次数。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, p, primes[MAX_N], cnt[MAX_N], ptot, cmod, pic[MAX_N], ai[MAX_N];

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y), t = x;
    x = y, y = t - (a / b) * y;
    return d;
}

int getInv(int a)
{
    int x, y;
    exgcd(a, cmod, x, y);
    return (x + cmod) % cmod;
}

int quick_pow(int bas, int tim)
{
    if (tim < 0)
        return quick_pow(getInv(bas), -tim);
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % cmod;
        bas = 1LL * bas * bas % cmod;
        tim >>= 1;
    }
    return ret;
}

int fac(int x, int mod)
{
    int ret = 1;
    for (int i = 1; i <= x; i++)
        if (i % mod != 0)
            ret = 1LL * ret * i % cmod;
    return ret;
}

int fac(int x, int mod, int &tot)
{
    // lucas;
    if (x < mod)
        return fac(x, mod);
    int seg = x / cmod, rem = x % cmod;
    int res = 1LL * quick_pow(fac(cmod - 1, mod), seg) * fac(rem, mod) % cmod;
    tot += x / mod;
    res = 1LL * res * fac(x / mod, mod, tot) % cmod;
    return res;
}

int binomial(int n_, int k_, int mod)
{
    int a = 0, b = 0, c = 0, res = 1;
    res = 1LL * res * fac(n_, mod, a) % cmod * getInv(fac(k_, mod, b)) % cmod * getInv(fac(n_ - k_, mod, c)) % cmod;
    return 1LL * res * quick_pow(mod, a - (b + c)) % cmod;
}

void factorize(int tmp)
{
    for (int i = 2; 1LL * i * i <= tmp; i++)
        if (tmp % i == 0)
        {
            primes[++ptot] = i;
            while (tmp % i == 0)
                cnt[ptot]++, tmp /= i;
        }
    if (tmp > 1)
        primes[++ptot] = tmp, cnt[ptot] = 1;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p), n += m;
    factorize(p);
    for (int i = 1; i <= ptot; i++)
    {
        cmod = 0x7fffffff, cmod = pic[i] = quick_pow(primes[i], cnt[i]);
        ai[i] = binomial(n, m, primes[i]);
    }
    cmod = 0x7fffffff;
    // begins to merge;
    for (int i = 2; i <= ptot; i++)
    {
        int x, y;
        exgcd(pic[i - 1], pic[i], x, y);
        pic[i] *= pic[i - 1];
        ai[i] = ((1LL * x * (ai[i] - ai[i - 1]) * pic[i - 1] % pic[i] + ai[i - 1]) % pic[i] + pic[i]) % pic[i];
    }
    printf("%d\n", ai[ptot]);
    return 0;
}

B - XOR-MIN-MAX

这道题很适合作为被 A 穿签到题,利用了分治的思想,很适合缺乏分治思维训练的选手。

我们可以设置任务$solve(dep, l, r)$为「确定最大值下标在$[l, r]$,正在处理第$dep$位」。具体如何理解呢?首先,显然高位的权要比低位的权要高,那么,如果这段区间中所有数的第$dep$位并不能被消成$0$,也就是这段区间内的数在第$dep$位存在$0, 1$两种情况,那么在$X_{dep}$中我们选$0, 1$都无法让最大值小于$2^{dep}$,那么我们可以分类讨论:把在$[l, r]$之间,$dep$这一位为$0, 1$的数字分类成集合$A, B$,然后把它们第$dep$位都赋为$1$。

如果$X$的第$dep$位为$0$,则最大值将会出现在集合$B$中,执行$solve(mid + 1, r, dep - 1)$;反过来同理。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, ai[MAX_N], ans = 0x7fffffff, tmp[MAX_N];

void solve(int l, int r, int dep)
{
    if (l > r)
        return;
    if (dep == -1)
    {
        int max_val = 0;
        for (int i = l; i <= r; i++)
            max_val = max(max_val, ai[i]);
        ans = min(ans, max_val);
        return;
    }
    int lptr = l, rptr = r, cnt0 = 0, cnt1 = 0;
    for (int i = l; i <= r; i++)
        if (ai[i] & (1 << dep))
            tmp[rptr--] = ai[i], cnt1++;
        else
            tmp[lptr++] = ai[i], cnt0++;
    if (cnt1 == (r - l + 1))
        for (int i = l; i <= r; i++)
            ai[i] = (tmp[i] ^ (1 << dep));
    else if (cnt0 == (r - l + 1))
        for (int i = l; i <= r; i++)
            ai[i] = tmp[i];
    else
        for (int i = l; i <= r; i++)
            ai[i] = (tmp[i] | (1 << dep));
    solve(l, lptr - 1, dep - 1), solve(lptr, r, dep - 1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    solve(1, n, 29);
    printf("%d\n", ans);
    return 0;
}

C - 平面上的点

$\Theta(n^2)$暴力还是很好写的,先枚举水平线,然后再分上下讨论;讨论中,我们都要从左往右枚举,但是我们有两个指针$lptr, rptr$,我们可以在过程中维护在$[lptr, rptr]$之间的颜色数始终严格小于$k$,然后再用点个数更新答案。

那么正解就没这么好写了。我们考虑在$k$中枚举一个被排除的颜色,然后分情况讨论:

  • 按$x$排序,相邻点对做垂直线,两线之间的点个数可能成为答案。
  • 向上看,我们可以把点按$y$降序排序,然后让矩形的横线段$[l, r]$强行$\in x_i$,也就是置横线段为当前点之上。用 multiset 查询当前点前驱后继的$x$作为矩形的横线范围,然后把当前点的$y + 1$作为基准线,用主席树查询当前矩形内的点数。
  • 向下看类似。

详细见代码:

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

int T, n, k, roots[MAX_N], yupper, gans;

struct point
{
    int x, y, c;
    bool operator<(const point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
} pts[MAX_N];

typedef multiset<point>::iterator mpit;

bool compareByY(const point &rhs1, const point &rhs2) { return rhs1.y < rhs2.y || (rhs1.y == rhs2.y && rhs1.x < rhs2.x); }

vector<point> ptByColor[MAX_N];
vector<int> mpx, mpy;

inline char nc()
{
    static char buf[10000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

namespace PST
{

struct node
{
    int lson, rson, val;
} nodes[MAX_N << 5];

int ptot;

int update(int qx, int l, int r, int pre)
{
    int p = ++ptot;
    nodes[p] = nodes[pre], nodes[p].val++;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid, nodes[pre].lson);
    else
        nodes[p].rson = update(qx, mid + 1, r, nodes[pre].rson);
    return p;
}

int query(int ql, int qr, int l, int r, int pre, int p)
{
    if (ql > qr)
        return 0;
    if (ql <= l && r <= qr)
        return nodes[p].val - nodes[pre].val;
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid)
        ret += query(ql, qr, l, mid, nodes[pre].lson, nodes[p].lson);
    if (mid < qr)
        ret += query(ql, qr, mid + 1, r, nodes[pre].rson, nodes[p].rson);
    return ret;
}

void init()
{
    ptot = 0;
    int last_ptr = 0;
    for (int i = 1, r = 0; i <= n; i = r + 1)
    {
        r = i, roots[pts[i].x] = update(pts[i].y, 1, yupper, last_ptr), last_ptr = roots[pts[i].x];
        while (r + 1 <= n && pts[r + 1].x == pts[i].x)
            r++, roots[pts[i].x] = update(pts[r].y, 1, yupper, last_ptr), last_ptr = roots[pts[i].x];
    }
}

} // namespace PST

int ripe(vector<int> &vec, int x) { return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1; }

void processCategory(int color)
{
    using namespace PST;
    if (ptByColor[color].empty())
        return (void)(gans = max(gans, n));
    sort(ptByColor[color].begin(), ptByColor[color].end());
    // horizontal intervals;
    gans = max(gans, query(1, yupper, 1, yupper, 0, roots[ptByColor[color].front().x - 1]));
    for (int i = 1, siz = ptByColor[color].size(); i < siz; i++)
    {
        point pt = ptByColor[color][i];
        gans = max(gans, query(1, yupper, 1, yupper, roots[ptByColor[color][i - 1].x], roots[pt.x - 1]));
        continue;
    }
    gans = max(gans, query(1, yupper, 1, yupper, roots[ptByColor[color].back().x], roots[mpx.size()]));
    // looking up;
    sort(ptByColor[color].begin(), ptByColor[color].end(), compareByY);
    multiset<point> ms;
    for (int siz = ptByColor[color].size(), i = siz - 1; i >= 0; i--)
    {
        mpit curt = ms.insert(ptByColor[color][i]);
        int baseLine = ptByColor[color][i].y + 1;
        int l, r;
        if (curt != ms.begin())
            curt--, l = curt->x, curt++;
        else
            l = 0;
        curt++;
        if (curt != ms.end())
            r = curt->x - 1;
        else
            r = mpx.size();
        curt--;
        gans = max(gans, query(baseLine, yupper, 1, yupper, roots[l], roots[r]));
    }
    ms.clear();
        // looking down;
    for (int siz = ptByColor[color].size(), i = 0; i < siz; i++)
    {
        mpit curt = ms.insert(ptByColor[color][i]);
        int baseLine = ptByColor[color][i].y - 1;
        int l, r;
        if (curt != ms.begin())
            curt--, l = curt->x, curt++;
        else
            l = 0;
        curt++;
        if (curt != ms.end())
            r = curt->x - 1;
        else
            r = mpx.size();
        curt--;
        gans = max(gans, query(1, baseLine, 1, yupper, roots[l], roots[r]));
    }
}

int main()
{
    T = read();
    while (T--)
    {
        n = read(), k = read();
        mpx.clear(), mpy.clear(), gans = 0;
        for (int i = 1; i <= n; i++)
        {
            pts[i].x = read(), pts[i].y = read(), pts[i].c = read();
            mpx.push_back(pts[i].x), mpy.push_back(pts[i].y);
        }
        sort(mpx.begin(), mpx.end()), mpx.erase(unique(mpx.begin(), mpx.end()), mpx.end());
        sort(mpy.begin(), mpy.end()), mpy.erase(unique(mpy.begin(), mpy.end()), mpy.end());
        yupper = mpy.size();
        for (int i = 1; i <= k; i++)
            ptByColor[i].clear();
        for (int i = 1; i <= n; i++)
        {
            pts[i].x = ripe(mpx, pts[i].x), pts[i].y = ripe(mpy, pts[i].y);
            ptByColor[pts[i].c].push_back(pts[i]);
        }
        sort(pts + 1, pts + 1 + n), PST::init();
        for (int i = 1; i <= k; i++)
            processCategory(i);
        printf("%d\n", gans);
    }
    return 0;
}

「FZOI」OI 周赛 #4 Div.1 - 题解

2020-01-04 18:17:51 By kal0rona

A - 对称的多边形

// std.cpp
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAX_N = 4e5 + 200;

int T, n, xi[MAX_N], yi[MAX_N], len[MAX_N];
ll seq[MAX_N];

ll getDist(int x1, int y1, int x2, int y2)
{
    return ll(x1 - x2) * ll(x1 - x2) + ll(y1 - y2) * ll(y1 - y2);
}

ll getAngle(int orgx, int orgy, int x1, int y1, int x2, int y2)
{
    ll dx1 = x1 - orgx, dy1 = y1 - orgy;
    ll dx2 = x2 - orgx, dy2 = y2 - orgy;
    return dx1 * dy2 - dx2 * dy1;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(len, 0, sizeof(len));
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &xi[i], &yi[i]);
        // create new string for manacher;
        for (int i = 0; i < n; i++)
        {
            seq[(i << 1) | 1] = getDist(xi[i], yi[i], xi[(i + 1) % n], yi[(i + 1) % n]);
            seq[(i << 1)] = getAngle(xi[i], yi[i], xi[(i + n - 1) % n], yi[(i + n - 1) % n], xi[(i + 1) % n], yi[(i + 1) % n]);
        }
        int tot_len = n << 1;
        for (int i = 0; i < n; i++)
            seq[i + tot_len] = seq[i];
        tot_len <<= 1;
        int R = 0, ans = 0, mid = 0;
        for (int i = 0; i < tot_len; i++)
        {
            if (i < R)
                len[i] = min(R - i, len[mid * 2 - i]);
            else
                len[i] = 1;
            while (i - len[i] >= 0 && i + len[i] < tot_len && seq[i + len[i]] == seq[i - len[i]])
                len[i]++;
            if (i + len[i] > R)
                R = i + len[i], mid = i;
            if (len[i] >= n + 1)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B - 最小方差树

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 2020;

int fa[MAX_N], n, m;
double ans = (double)(0x3f3f3f3f);

struct edge
{
    int from, to, weight;
    double cmp;
    bool operator<(const edge &d) const { return cmp < d.cmp; }
} edges[MAX_N];

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

void kruskal(double avg)
{
    double sqr = 0;
    double len = 0;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
        edges[i].cmp = 1.0 * (avg - 1.0 * edges[i].weight) * (avg - 1.0 * edges[i].weight);
    sort(edges + 1, edges + 1 + m);
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= m; i++)
    {
        int x = edges[i].from, y = edges[i].to;
        if (find(x) != find(y))
            fa[fa[x]] = fa[y], cnt++, len += edges[i].weight, q.push(i);
    }
    len /= (n - 1);
    while (!q.empty())
    {
        int u = q.front();
        sqr += (edges[u].weight - len) * (edges[u].weight - len);
        q.pop();
    }
    if (cnt == n - 1)
        ans = min(ans, sqrt(sqr / (n - 1)));
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &edges[i].from, &edges[i].to, &edges[i].weight);
    for (double avg = 0.25; avg <= 100; avg += 0.25)
        kruskal(avg);
    printf("%.4lf", ans);
    return 0;
}

C - 数列计数

为啥你们都写得那么复杂?其实发现容斥+DP就可以比较轻松的做出来了。我们发现先算和为$p$的倍数的任意方案数,然后再减去只用质数的方案数就是答案。

第一部分

第一部分的式子并不难,设置$dp[i][j]$为前$i$个数的和在模意义下为$j$的方案数,那么转移如下: $$ dp[i][j] = \sum_{k = 0}^{p - 1} dp[i - 1][(j - k) \bmod p] \times c_k $$ 其中$c_k$就是在$m$的值域内选模意义下为$k$的方案数。根据题意,$c_k$也比较显然: $$ c_k = \begin{cases} \lfloor \frac{m}{p} \rfloor, k = 0 \\ \lfloor \frac{m - k}{p} \rfloor + 1, k < m \\ 1, k = m \\ 0, k > m \end{cases} $$ 因为序列长度很长,那么我们可以考虑构建矩阵来优化之: $$ dp'[0][j] = \sum_{k = 0}^{p - 1} dp[0][j - k \bmod p] \times c_k \\ dp'[0][j] = \sum_{k = 0}^{p - 1} dp[0][k] \times c_{(j - k \bmod p)} $$ 再参考矩阵乘法的意义: $$ A[i][j] = \sum_{k = 0}^{p - 1} B[i][k] \times C[k][j] $$ 那么我们的矩阵其实就很好构造: $$ trans[k][j] = c_{(j - k \bmod p)} $$

第二部分

第二部分差不多,我们需要线性筛把$m$内的质数筛出来,然后在桶里计数:$bucket[i \bmod p]++$。之后在$trans$矩阵内减去这些质数的方案数,做一遍即可。

代码

// P3702.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110, MAX_M = 2e7 + 200, mod = 20170408;

int primes[MAX_M], tot, n, m, p, table[MAX_N];
bool vis[MAX_M];

struct matrix
{
    int mat[MAX_N][MAX_N];

    matrix() { memset(mat, 0, sizeof(mat)); }

    int *operator[](const int &rhs) { return mat[rhs]; }

    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        for (int i = 0; i < p; i++)
            for (int j = 0; j < p; j++)
                for (int k = 0; k < p; k++)
                    ret[i][j] = (1LL * ret[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }

    matrix operator^(const int &rhs)
    {
        int tim = rhs;
        matrix ret, bas = *this;
        for (int i = 0; i < p; i++)
            ret[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                ret = ret * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ret;
    }
} dp, trans;

void sieve()
{
    for (int i = 2; i <= m; i++)
    {
        if (!vis[i])
            primes[++tot] = i;
        for (int j = 1; j <= tot && 1LL * i * primes[j] <= m; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= tot; i++)
        table[primes[i] % p]++;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    sieve();
    for (int c = 0; c < p; c++)
        for (int b = 0; b < p; b++)
        {
            int delta = (c - b + p) % p;
            if (delta == 0)
                trans[b][c] = m / p;
            else if (delta < m)
                trans[b][c] = int((m - delta) / p) + 1;
            else if (delta == m)
                trans[b][c] = 1;
            else
                trans[b][c] = 0;
            trans[b][c] %= mod;
        }
    dp[0][0] = 1, dp = dp * (trans ^ n);
    int ans = dp[0][0];
    memset(dp.mat, 0, sizeof(dp.mat));
    memset(trans.mat, 0, sizeof(trans.mat));
    for (int c = 0; c < p; c++)
        for (int b = 0; b < p; b++)
        {
            int delta = (c - b + p) % p;
            if (delta == 0)
                trans[b][c] = m / p;
            else if (delta < m)
                trans[b][c] = int((m - delta) / p) + 1;
            else if (delta == m)
                trans[b][c] = 1;
            else
                trans[b][c] = 0;
            trans[b][c] = (trans[b][c] + mod - table[delta]) % mod;
        }
    dp[0][0] = 1, dp = dp * (trans ^ n);
    ans = (ans + mod - dp[0][0]) % mod;
    printf("%d\n", ans);
    return 0;
}

HNOI 2018 省队集训 Day 1 - 解题报告

2019-12-20 21:34:04 By kal0rona

A - Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 $1$ 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 $root$ 时,$u, v$ 之间的 $LCA$ 显然是 $lca(u, v), lca(root, u), lca(root, v)$ 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

// QOJ2030.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 3e5 + 200;

int n, q, seq[MAX_N], lft[MAX_N], rig[MAX_N], anti[MAX_N], root, fa[20][MAX_N], head[MAX_N], current;
int dep[MAX_N], ptot;

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

namespace SegmentTree
{

ll nodes[MAX_N << 2], tag[MAX_N << 2];
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(nodes[p] = seq[anti[l]]);
    build(l, mid, lson), build(mid + 1, r, rson);
    nodes[p] = nodes[lson] + nodes[rson];
}

void pushdown(int p, int l, int r)
{
    if (tag[p] != 0)
    {
        tag[lson] += tag[p], tag[rson] += tag[p];
        nodes[lson] += 1LL * tag[p] * (mid - l + 1), nodes[rson] += 1LL * tag[p] * (r - mid);
        tag[p] = 0;
    }
}

void update(int ql, int qr, int l, int r, int p, ll val)
{
    if (ql <= l && r <= qr)
    {
        nodes[p] += 1LL * (r - l + 1) * val, tag[p] += val;
        return;
    }
    pushdown(p, l, r);
    if (ql <= mid)
        update(ql, qr, l, mid, lson, val);
    if (mid < qr)
        update(ql, qr, mid + 1, r, rson, val);
    nodes[p] = nodes[lson] + nodes[rson];
}

ll query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return nodes[p];
    pushdown(p, l, r);
    ll ret = 0;
    if (ql <= mid)
        ret += query(ql, qr, l, mid, lson);
    if (mid < qr)
        ret += query(ql, qr, mid + 1, r, rson);
    return ret;
}

#undef mid
#undef rson
#undef lson

} // namespace SegmentTree

void dfs_init(int u, int fat)
{
    dep[u] = dep[fat] + 1, fa[0][u] = fat, lft[u] = ++ptot, anti[ptot] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat)
            dfs_init(edges[i].to, u);
    rig[u] = ptot;
}

int getLCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y])
            x = fa[i][x];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}

int main()
{
    memset(head, -1, sizeof(head)), root = 1;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs_init(1, 0), root = 1, SegmentTree::build(1, n, 1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    while (q--)
    {
        int opt, x, y, z;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
            root = x;
        else if (opt == 2)
        {
            scanf("%d%d", &y, &z);
            int lca = getLCA(x, y), lca1 = getLCA(root, x), lca2 = getLCA(root, y);
            int dlca = (dep[lca1] > dep[lca2] ? lca1 : lca2);
            if (dep[lca] > dep[dlca])
                dlca = lca;
            if (dlca == root)
                SegmentTree::update(1, n, 1, n, 1, z);
            else if (lft[dlca] <= lft[root] && rig[root] <= rig[dlca])
            {
                int u = root;
                for (int i = 19; i >= 0; i--)
                    if (dep[fa[i][u]] > dep[dlca])
                        u = fa[i][u];

                SegmentTree::update(1, n, 1, n, 1, z);
                SegmentTree::update(lft[u], rig[u], 1, n, 1, -z);
            }
            else
                SegmentTree::update(lft[lca], rig[lca], 1, n, 1, z);
        }
        else if (opt == 3)
        {
            // something different;
            // if there is an ancestor relationship;
            if (x == root)
                printf("%lld\n", SegmentTree::nodes[1]);
            else if (lft[x] <= lft[root] && lft[root] <= rig[x])
            {
                int u = root;
                for (int i = 19; i >= 0; i--)
                    if (dep[fa[i][u]] > dep[x])
                        u = fa[i][u];
                printf("%lld\n", SegmentTree::nodes[1] - SegmentTree::query(lft[u], rig[u], 1, n, 1));
            }
            else
                printf("%lld\n", SegmentTree::query(lft[x], rig[x], 1, n, 1));
        }
    }
    return 0;
}

B - Function

我们回顾一下式子: $$ f(x, y) = \begin{cases} A_y & x = 1 \\ f(x-1, y) + A_y & y = 1 \text{ and } x \neq 1 \\ \min \{ f(x-1, y-1), f(x-1, y) \} + A_y & \text{otherwise} \end{cases} $$ 我们可以近似地认为,这个式子的意义为在网格图上从 $(x, y)$ 走到 $(1, 1)$ 的最短距离。可以大概猜到一个结论:这样的路径一定是先走一段连续的左上角,再停在一个相对较小的权值上直走向上。那么,假设停止时,$y = i$,那么答案就是: $$ \text{设 } p[n] = \sum_{i = 1}^n A_i, ans = A_i(x - y + i) + p[y] - p[i] $$ 我们整理一下: $$ A_i(x - y) + A_i \cdot i + p[y] - p[i] $$ 我们可以把 $(x - y)$ 看做自变量,然后把这些直线丢入平面空间中。我们需要把询问离线排序,然后我们只需要保留最小的直线,也就是下凸包,这样可以让答案最小,用单调栈维护,并在栈上二分在其定义域中的直线并求值即可。

// QOJ2031.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 5e5 + 200;

int n, q, stk[MAX_N << 1], tail;
double pos[MAX_N << 1];
ll ai[MAX_N], prefix[MAX_N], constSuf[MAX_N], ans[MAX_N];

struct query
{
    int x, y, id;
    bool operator<(const query &rhs) const { return y < rhs.y; }
} queries[MAX_N];

double calc(int x, int y) { return double(constSuf[y] - constSuf[x]) / double(ai[x] - ai[y]); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &ai[i]), prefix[i] = prefix[i - 1] + ai[i];
        constSuf[i] = ai[i] * i - prefix[i];
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &queries[i].x, &queries[i].y), queries[i].id = i;
    sort(queries + 1, queries + 1 + q);
    int curt = 0;
    for (int i = 1; i <= q; i++)
    {
        int delta = queries[i].x - queries[i].y;
        while (curt + 1 <= queries[i].y)
        {
            curt++;
            while (tail > 0 && ai[stk[tail]] >= ai[curt])
                tail--;
            while (tail > 1 && calc(curt, stk[tail]) > calc(stk[tail], stk[tail - 1]))
                tail--;
            stk[++tail] = curt;
            if (tail > 1)
                pos[n - tail] = calc(curt, stk[tail - 1]);
        }
        int idx = n - (lower_bound(pos + n - tail, pos + n - 1, delta) - pos);
        ans[queries[i].id] = delta * ai[stk[idx]] + constSuf[stk[idx]] + prefix[curt];
    }
    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

C - Or

很显然的 DP 式子,设置 $dp[i][j]$ 为前 $i$ 个序列中已经选择了 $j$ 位 $1$ 的合法状态。正常的转移非常简单: $$ dp[i][j] = \sum_{c = 1}^j dp[i - 1][j - c] {j \choose c} 2^{j - c} $$ 其中,$c$ 为这次新增的 $1$ 的个数。这样的转移是 $\Theta(nk^2)$ 的。然而,我们发现这个式子的卷积形式非常明显: $$ \begin{aligned} dp[i][j] &= \sum_{c = 1}^j \frac{ dp[i - 1][j - c] 2^{j - c} } { (j - c)! } \cdot \frac{j!}{c!} \\ \frac{dp[i][j]}{j!} &= \sum_{c = 1}^j \frac{dp[i - 1][j - c] 2^{j - c}}{(j - c)!} \cdot \frac{1}{c!} \end{aligned} $$ 稍微设置一下: $$ \begin{aligned} A_i(x) &= \sum_{j = 0}^\infty \frac{dp[i][j]}{j!} x^j = \sum_{j = 0}^\infty x^j \sum_{c = 1}^j \frac{dp[i - 1][j - c]2^{j - c}}{(j - c)!} \cdot \frac{1}{c!} \\ F_i(x) &= \sum_{c = 0}^\infty \frac{dp[i - 1][c]2^c}{c!} x^c, G_i(x) = \sum_{c = 0}^\infty \frac{1}{c!} x^c \\ A_i(x) &= F_i(x)G_i(x) \end{aligned} $$ 调用 $n$ 次 NTT 即可算完。但是这样非常的缓慢,我们需要利用更多已有的信息。我们注意到: $$ \begin{aligned} A_i(2x) &= \sum_{c = 0}^\infty \frac{dp[i - 1][c]}{c!} (2x)^c = \sum_{c = 0}^\infty \frac{dp[i - 1][c]2^c}{c!} x^c \\ &= F_i(x) \end{aligned} $$ Splendid!调整一下: $$ A_i(x) = F_i(x)G_i(x) = A_i(2x)G_i(x) $$ 我们可以递归来算,这样复杂度就是 $\Theta(n \log n \log k)$ 的了。

// QOJ2032.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, mod = 998244353, G = 3;

int n, K, poly_bit, poly_siz, rev[MAX_N], fac[MAX_N], fac_inv[MAX_N], pow2[MAX_N];
int f[MAX_N], g[MAX_N];

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

const int Gi = quick_pow(G, mod - 2);

void ntt_initialize()
{
    for (int i = 0; i < poly_siz; i++)
        rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (poly_bit - 1)));
}

void ntt(int *arr, int dft)
{
    for (int i = 0; i < poly_siz; i++)
        if (i < rev[i])
            swap(arr[i], arr[rev[i]]);
    for (int step = 1; step < poly_siz; step <<= 1)
    {
        int omega_n = quick_pow((dft == 1 ? G : Gi), (mod - 1) / (step << 1));
        for (int j = 0; j < poly_siz; j += (step << 1))
        {
            int omega_nk = 1;
            for (int k = j; k < j + step; k++, omega_nk = 1LL * omega_nk * omega_n % mod)
            {
                int t = 1LL * arr[k + step] * omega_nk % mod;
                arr[k + step] = (0LL + arr[k] + mod - t) % mod;
                arr[k] = (1LL * arr[k] + t) % mod;
            }
        }
    }
    if (dft == -1)
    {
        int inv = quick_pow(poly_siz, mod - 2);
        for (int i = 0; i < poly_siz; i++)
            arr[i] = 1LL * arr[i] * inv % mod;
    }
}

void polyMultiply(int *A, int *B)
{
    ntt(A, 1), ntt(B, 1);
    for (int i = 0; i < poly_siz; i++)
        A[i] = 1LL * A[i] * B[i] % mod;
    ntt(A, -1);
    for (int i = 0; i < poly_siz; i++)
        B[i] = 0;
    for (int i = K + 1; i < poly_siz; i++)
        A[i] = 0;
}

void multiply(int *A, int coeff)
{
    for (int i = 0, acc = 1; i <= K; i++, acc = 1LL * acc * coeff % mod)
        A[i] = 1LL * A[i] * acc % mod;
}

void solve(int idx)
{
    if (idx == 0)
        return (void)(f[0] = 1);
    if (idx & 1)
    {
        solve(idx - 1), g[0] = 0;
        for (int i = 1; i <= K; i++)
            g[i] = fac_inv[i];
        multiply(g, quick_pow(2, idx - 1));
        polyMultiply(f, g);
    }
    else
    {
        solve(idx >> 1);
        for (int i = 0; i <= K; i++)
            g[i] = f[i];
        multiply(g, quick_pow(2, idx >> 1));
        polyMultiply(f, g);
    }
}

int main()
{
    scanf("%d%d", &n, &K);
    for (int i = fac[0] = 1; i <= K; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[K] = quick_pow(fac[K], mod - 2);
    for (int i = K - 1; i >= 0; i--)
        fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod;
    for (int i = pow2[0] = 1; i <= max(n, K); i++)
        pow2[i] = 2LL * pow2[i - 1] % mod;
    while ((1 << poly_bit) <= (K << 1))
        poly_bit++;
    poly_siz = (1 << poly_bit), ntt_initialize();
    solve(n);
    int ans = 0;
    for (int i = n; i <= K; i++)
        ans = (1LL * ans + 1LL * f[i] * fac[K] % mod * fac_inv[K - i] % mod) % mod;
    printf("%d\n", ans % mod);
    return 0;
}

总结

我认为这是一套比较好的入门省选训练题,不会过于毒瘤也不会过于偏向联赛,科技题也不会过于裸露,而签到题也很友好。

kal0rona Avatar