2021.4.18 - 4.24 一周小结

这周做的题目，难度总体都挺高的，集中在 CF 上 3000 左右。并且在通过之前没有看任何一题的题解！（得瑟一下！）其实，有些难题，多想想，还是能艹过去的！Try a Try, AC is OK.（bushi）至于为什么看这些 CF 评级比较高的题呢？因为感觉评分高一些的题，在题目风格上更加 OI 一些，也更是我所擅长的。

CF1408I. Bitwise Magic

题意：

$n,k,c$ $n$ $a$ （保证元素互不相同）。
$k$ $a_i$ $-1$ $x=0,1~...~2^c-1$ $x$ $998244353$ 取模。
$k,c\le 16,a_i\in [k,2^c),n\le 2^c-k$

题解：

$x^ay^b\times x^cy^d=x^{a+c}y^{b\wedge d}$ $\sum\sum \frac 1{a!}x^ay^b$ ：于是问题就可以转化成快速求多个二元多项式的乘积。但是这么想是没有必要的，我有一个更加巧妙而简洁的做法：

$i$ $d_i$ $d\{\}$ ，它出现的可能性可以用可重排列计算：

P(d\{\})=k!\cdot\left(\prod_{i=1}^nd_i!\right)^{-1}\cdot \left(\frac 1n\right)^k

$f_{i,j,S}$ $i$ $j$ $S$ $S=\sum\limits_{p=1}^ia_i\wedge(a_i-d_i)$ $2^c\times 2^c\times k^2$ 的做法。考虑如何加速。

$n\times |S|\times k^2$ ；2.每个数等价，所以不按顺序统计不影响答案。

$S$ 的值域很小，段内可以快速 DP；最后再想办法拼起来。

$k\le 16$ $S$ $15\times 2$ $2k\times n\times k^2$ 。

$9$ $(c-k)\times 2^c\times c\times k^2$ 。

评测链接：AC submission：https://codeforces.ml/contest/1408/submission/113971716.

UPD：事后 zc_li 强神告诉我说直接对第二维 fwt 一下就行了，我傻了。

CF1474F 1 2 3 4 ...

题意：

给定一个序列，求其中最长严格上升子序列长度及其个数。
$n(1\leq n\leq 50)$ $x(-10^9\leq x\leq 10^9)$ $n$ $d_i(-10^9\leq d_i\leq 10^9)$ $d_i\ge 0$ $d_i$ $+1$ $d_i<0$ $-d_i$ $-1$ 的值。

题解：

$10^5$ $f_i$ $i$ $x$ $f_{x}+=\max(f_{x-1},1)$ $\sum\limits_{j=1}^i d_j-\min\limits_{k=1}^{i-1}\{\sum_{j=1}^kd_j\}=max$ $i$ $f$ $i$ $f$ $f$ 数组清空。

$[pos_i,pos_{i-1}]$ 这一段平移一下加到自己身上；上升操作，相当于把区间的第一个数加上一个数，然后把这个区间前缀和一下。

$f$ $O(n)$ $f_x$ $O(n)$ $f(x)$ 表示。下面大致口胡一下：

1,1,1,... $f(x)=1$ 表示。
$f(x)=\frac{(1+x)x}2$ $f(x)=\frac{(2x+1)(x+1)x}6$ 表示。...... 它的任意一阶前缀和都可以用多项式表示。
$f$ $f(x)+f(x-1)$ 表示；第一个数可以单独拆成一个常数多项式。
$f$ 可以看作是序列 1,1,1,... 的多阶前缀和的多项式的和。

$f$ $f$ $n$ $f$ 直接拉格朗日插值插出来。

$f$ 已经超出了原来的范围，那么就需要新建一个常数多项式来表示这一段。

评测链接：AC submission：https://codeforces.ml/problemset/submission/1474/113669336.

CF1476F. Lanterns

题意：

$n$ $i$ $p_i$ $[i - p_i,i - 1]$ $[i + 1, i + p_i]$ 的灯笼。
$n\le 3\times 10^5$ 。

题解：

$n^2\log n$ $n=300000$ 。

$O(n^3)$ $f_{i,l,r}$ $i$ $l$ $r$ 的一个状态，然后就可以快乐地 DP 了。

$l$ $r$ $O(n^2)$ 。

$i$ $l$ $l$ 我才会使它朝左，所以我们从左往右只保留这些合法状态来 DP，大致代码如下：


xxxxxxxxxx
13
1
for (int i = 1; i <= n; i++)
2
{
3
    sort(dp[i - 1].begin(), dp[i - 1].end(), [](node x, node y) { return x.l == y.l ? x.r > y.r : x.l > y.l; });
4
    int mx = -1e9;
5
    for (int j = 0; j < dp[i - 1].size(); j++)
6
    {
7
        node u = dp[i - 1][j];
8
        if (u.r <= mx) continue;
9
        if (u.l >= i - p[i] && u.l != i) dp[i].push_back({ u.r < i ? i : n + 1, u.r, j, 0 });
10
        dp[i].push_back({ min(u.l, u.r < i ? i : n + 1), max(u.r, i + p[i]), j, 1 });
11
        mx = max(mx, u.r);
12
    }
13
}