2019.5.16

Veröffentlicht am

我想欣赏人类的心智荣耀，想要在纷繁复杂变化的世界上多看一眼永恒不变的星辰大海

情侣？给我烧了！

题目描述

有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2×n$ 个座位。
现在，每个人将会随机坐在某一个位置上，且恰好将这 $2 × n$ 个座位坐满。
如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。
你的任务是求出当 $k = 0, 1, … , n$ 时，共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。
两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2n)!$ 种不同的就坐方案。

输入输出格式

输入格式：
输入包含多组数据。
输入的第一行包含一个正整数 $T(1 \leq T \leq 1000)$，表示数据的组数。
接下来 $T$ 行，每行包含一个正整数 $n(1 \leq n \leq 1000)$。
输出格式：
对于每组输入数据，输出共 $n + 1$ 行，每行包含 $1$ 个整数，分别表示 $k = 0, 1, …, n$ 时满足恰好有 $k$ 对情侣是和睦的就坐方案数。由于结果可能较大，因此输出对 $998244353$ 取模的结果。

输入输出样例

输入样例#1：
2
1
2

输出样例#1：
0
2
16
0
8

题解

这道题大概算是入门组合数题？？

推一推k=0找感觉。然后发现答案非常简单（只需要注意每个人是不同的）

对于每一个询问 $k$ ，记 $g(x)$ 表示 $x$ 对情侣都错开的方案总数，那么答案可以写成如下形式：

从$n$个位置选$k$个，然后考虑顺序，然后前后都是不同的，然后剩下的都错开。

由乘法原理得到答案。

$g(x)$怎么求呢？$O(n)$容斥就好。

$g(x) = (2x)! - \sum\limits_{i=1}^{x}f(i)$

至于这个怎么互相推实现我就懒得管了，反正肯定是对的

时间复杂度$O(n^2)$，用这个方法先预处理所有答案。

情侣？给我烧了！（加强版）

题目描述

有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2×n$ 个座位。
现在，每个人将会随机坐在某一个位置上，且恰好将这 $2 × n$ 个座位坐满。
如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。
你的任务是求出共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。
两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，在没有任何限制条件的情况下，每个人任意就坐一共会有 $(2n)!$ 种不同的就坐方案。

输入输出格式

输入格式：
输入包含多组数据。
输入的第一行包含一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行包含两个非负整数 $n, k$，其意义见题目描述。
输出格式：
对于每组输入数据，输出一行，表示对应的就坐方案数。由于结果可能较大，因此输出对 $998244353$ 取模的结果。
输入输出样例

输入样例#1：
5
1 1
2 0
2 2
2333 666
2333333 1000000

输出样例#1：
2
16
8
798775522
300377435

说明

对于 $10 \%$ 的数据，满足 $1 \leq T \leq 10, 1 \leq n \leq 5$
对于 $40 \%$ 的数据，满足 $1 \leq n \leq 3 \times 10^3$
对于 $100 \%$ 的数据，满足 $1 \leq T \leq 2 \times 10^5, 1 \leq n \leq 5 \times 10^6, 0 \leq k \leq n$

题解

和上面题意一样，但是复杂度不够优秀。看到了998244353

然后我被迫抄题解了。

有一个高端的数学做法，显然是有过数学竞赛或深厚数学背景的人写的，如下：

给出一个生成函数爆算递推式的方式：
不妨设 $D_n$ 是这个问题的“错排”：每对情侣都不在一排的方案数。那么对于答案 $f(n, k)$ 来说就可以用 $D_n$ 进行表示，即考虑坐在一排的情侣是哪几对且他们在哪几排，即

这自然而然地导出了恒等式

其中 $\binom nk^2$ 引导我们将生成函数写成

那么因为

带入原始，我们得到了 $D(z)$ 的生成函数方程

因此

这帮助我们得到一个式子用于计算 $D_n$（其实就是容斥）

或者也可以直接卷积，但是这都不够快速。我们考虑对 $D(z)$ 进行求导。

这个微分方程可以帮助我们写出 $D(z)$ 的递推形式了，即

提取系数有

最后那步应该是作者省略了微分方程解的方法，总之这个方法让我只能感叹神。

第二种只用了初级组合知识我还是没能自己想出来

之前的弱化版的我们直接用一个$n^2$的$DP$求取错排的方案数即可，但是这里不行。
我们先算出刚好$K$个配对的方案数量，然后乘以剩下的错排方案数，但是这个显然不是简单的错排了，因此不能直接套用公式。
前面的刚好$K$个配对的就是：

选$k$排座位$C_n^k$
选$k$对情侣$C_n^k$
这$k$对每排可以交换坐$2^k$
这$k$排可以任意排列$k!$

所以前半部分的答案就为$(C_n^k)^2\times k!\times 2^k$
那么对于错排部分，我们模仿错排递推的推导过程分类考虑，我们令$g[n]$为$n$对不匹配的方案数：
首先我们看第一排坐两个不是情侣的人，不难发现，那么可以有$2n\times(2n-2)$种选法，剩下只有$n-1$个座位，对于剩下的，我们考虑另外的两个（就是与开始那两个坐在一起的另一半情侣），他们有两种方案：

坐在一起：就是在剩下的$n-1$排中任选一排，且这个两个人可以交换，然后就转化为子问题$g[n-2]$，所以贡献为$2\times (n-1)\times g[n-2]$
不坐在一起，我们就把他们又看作一个不能在一起的错排问题，于是贡献为$g[n-1]$

和错排公式结合起来，所以这部分的方案数贡献为$2n(2n-2)\left(g[n-1]+2(n-1)g[n-2]\right)$
那么答案就是$(C_n^k)^2\times k!\times 2^k\times 4n(n-1)\left(g[n-1]+2(n-1)g[n-2]\right)$
预处理阶乘和阶乘逆元还有$g$函数和$2$的幂，然后每次$O(1)$的回答即可。
复杂度为$O(logMod+n+T)$
其中的$logMod$为处理一个阶乘的逆元。

好烦，难题只会抄题解

忘情

我们定义一段序列的值为这个，其中 $n$为此序列的元素个数。
我们给定一段长度为 $n$ 的序列,现在要求将它分成 $m$ 段，要求每一段的值的总和最小，求出这个最小值。
输入输出格式
输入格式：
第一行两个正整数，分别为 $n$，$m$，定义见题面。
接下来一行为 $n$ 个正整数，依次给出这个序列的每个元素的值 $x_i$ 。
输出格式：
一个整数，求出这个最小值。
输入输出样例

输入样例#1：
3 2
1 2 3

输出样例#1：
32

输入样例#2：
10 3
1 2 3 4 5 6 7 8 9 10

输出样例#2：
1140

说明

对于 $30 \%$ 的数据，$m≤n≤500$；

另有 $20 \%$ 的数据，保证 $m=2$；

对于 $100 \%$ 的数据，$m≤n≤100000$，$1≤x_i≤1000$。

题解

这题还好还是看了题解的wqs

暴力不说了，序列分割？

首先化简式子。
$\frac{((\sum{i=1}^nx_i\times \overline{x})+\overline{x})^2}{\overline{x}^2}$
$=(\sum{i=1}^nxi+1)^2$
设$f{i,j}$表示前$i$个数分成$j$段的最小价值，$O(n^2)$暴力就行了。

设$f_i$表示若干段好了，那样空间可以了。

到此为止都是序列分割。

然后出题人不知怎么证明的给每个$f_i$加值能和段数反相关。

然后就解决了。。

偷来出题人的标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>

#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define dwn(I, A, B) for (int I = (A); I >= (B); --I)
#define erp(I, X) for (int I = head[X]; I; I = next[I])

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
    read(t); read(args...); 
}
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
template <typename T> void writeln(T x) {
    write(x);
    puts("");
}
template <typename T> inline bool chkMin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkMax(T& x, const T& y) { return x < y ? (x = y, true) : false; }

typedef long long LL;
const int maxn = 1e5 + 207;
const LL inf = 1e16;
LL s[maxn], f[maxn];
int q[maxn], cnt[maxn];
int n, m;

inline double y(int i) { return f[i] + s[i] * s[i]; }
inline double x(int i) { return s[i]; }
inline double k(int i) { return 2.0 * (s[i] + 1); }
inline double slope(int i, int j) {
    return (y(i) - y(j)) / (x(i) - x(j));
}
inline bool check(LL mid) {
    int head = 0, tail = 0;
    rep(i, 1, n) {
        while (head < tail && slope(q[head], q[head + 1]) < k(i)) ++head;
        int j = q[head];
        // 注意这里在dp方程后面要加mid
        f[i] = f[j] + (s[i] - s[j] + 1) * (s[i] - s[j] + 1) + mid;
        cnt[i] = cnt[j] + 1;
        while (head < tail && slope(q[tail - 1], q[tail]) > slope(q[tail], i)) --tail;
        q[++tail] = i;
    }
    return cnt[n] > m;
}

int main() {
    read(n, m);
    rep(i, 1, n) read(s[i]), s[i] += s[i - 1];
    LL left = 0, right = inf, ans;
    while (left <= right) {
        LL mid = (left + right) >> 1;
        if (check(mid)) left = mid + 1;
        else ans = mid, right = mid - 1;
    }
    check(ans);
    writeln(f[n] - ans * m);
    return 0;
}