大脑宕机了！错误已更正，感谢提醒！
---
[更好的阅读体验？]()
---
A.木棍切割 1
我现在很难解释我的做法，只能说 n^3 大标之后就很容易推出柿子了。现在还不知道怎么证明正确性qwq
以及如果模拟赛你去洛谷找原，找到的不是这个，是木棍切割 2，如果看看题面的话就不会掉进坑里。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main()
{
scanf("%lld", &n);
if(n & 1) puts("0");
else
{
if(n % 4 == 0) printf("%lld", n / 4 * 6 - 5);
else printf("%lld", (n - 2) / 4 * 6);
}
return 0;
}
```
---
B.第 k 小
用 dp 的思想。f[i][j] 表示前 i 位中 1 的个数最多有 j 个的答案方案数。边界为 ```f[0][i] = 1, f[i][0] = 1;```，此时答案分别为该数字长度为 0、该数字全是 0。
转移方程比较好理解：对于 f[i][j]，当 j <= i 时才可能更新答案，考虑这一位选 1 还是选 0，分别对应 f[i - 1][j - 1] 和 f[i - 1][j]。否则答案同 f[i][i]。
接下来需要构造答案，感觉思维上比较有难度。
1.我们需要构造长度为 n 且 1 的个数不超过 m 的第 k 小数。从最高位到最低位枚举长度，**所以当前位选 1 一定大于选 0**。
**2.对于第 k 小，我们需要把这个数从 f[1 ~ n][0 ~ m] 这些所存方案数中拼出来。**
3.若 k > f[i - 1][j] ，我们这一位即使放了 1 也满足不了答案。所以直接放 1，然后把这部分方案从 k 中减掉。
4.若 k < f[i - 1][j] ，那就不能放 1，若放了 1 方案数就超过要求了。
稍微绕了点弯，感觉不好想，但算一种比较典的拼凑思路罢。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, k;
ll f[32][32];
int main()
{
scanf("%d%d%lld", &n, &m, &k);
for(int i = 0; i <= n; i ++ )
{
f[i][0] = 1;
f[0][i] = 1;
}
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ )
{
if(j <= i) f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
else f[i][j] = f[i][i];
}
}
int i = n, j = m;
while(i)
{
if(k > f[i - 1][j] && k)
{
printf("1");
k -= f[i - 1][j];
j --;
}
else printf("0");
i --;
}
return 0;
}
```
感觉本题非常聪明，我叹为观止，大受震撼。是我太愚笨了。但模拟赛本题纯暴力枚举 k 就能拿到 70pts 感觉非常有实力。赛时写了不严格 O(n) 枚举，但显然 K 巨大所以炸了是情理之中。但暴力能有这么多分是我没想到的。
---
C.蚂蚁掉头
又是很精妙的题，愈发显得我像一个脑瘫的很棒的题。
考虑数形结合。在数轴上，向右走是向右上走，向左走是向右下。
我们以 $N = 2$ 时来举例。那么画出来的图大概会长这个样子。
蓝色线将它们分成两层，分别表示两个小区间。黄色表示路径，而粉色圈出来的“尖”是转折点，表示蚂蚁掉一次头。既然我们要求最小的调头次数，那就要最少的“尖”。
通过手动枚举（你自己画画图试试），我们发现这两层中，上一层的尖的个数、下一层承接尖的“台”个数都固定。因此确定方案数，就是确定哪个尖放在哪个台上。（注意，尖和台的样子都固定，所以个体之间没有差异；一个台可以放多个尖，也可以有台空着不放，自己形成一个下层尖。）尖、台的个数是 a[i] / 2。
可以类比将 n 个苹果放到 m 个篮子里。
1.$n > m$：为了不产生新的“尖”，那就让每个台上都至少放一个尖。根据插板法，将尖分成 m 块，即在尖之间 n - 1 个空里放 m - 1 个插板。$$ ans = ans * {C_{a[i + 1] - 1}^{a[i] - 1}}$$
2.$n <= m$：为了不让台产生（下面一层）新的“尖”，那就让每个台上都尽量有尖。即在 m 个位置里选 n 个。
$ans = ans * C_{a[i]}^{a[i+1]}$
这里只是两层。同理，如果扩展到多层，可以把“台”看成新的“尖”，与下面的“台”再进行配对。每层之间的选择互不影响，所以根据乘法原理把它们都乘起来就是总方案数。
至于乘的过程中可能会出现 0，那就把 jc[0] 设为 1即可。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
int n;
int a[N];
ll jc[N];
ll pmod(ll a, ll b)
{
ll tot = 1;
while(b)
{
if(b & 1) tot = (tot * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return tot % mod;
}
ll C(ll x, ll y)
{
return jc[x] * pmod(jc[y], mod - 2) % mod * pmod(jc[x - y], mod - 2) % mod;
}
int main()
{
ll ans = 1;
scanf("%d", &n);
for(int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
if(a[i] & 1)
{
cout << "0";
return 0;
}
a[i] /= 2;
}
jc[0] = 1;
for(int i = 1; i <= 1000000; i ++ ) jc[i] = (jc[i - 1] % mod * i % mod) % mod;
for(int i = 1; i < n; i ++ )
{
if(a[i + 1] > a[i]) ans = (ans * C(a[i + 1] - 1, a[i] - 1)) % mod;
else ans = (ans * C(a[i], a[i + 1])) % mod;
}
printf("%lld", ans);
return 0;
}
```
---
D.区间
不好评价，爆锤我自己，赛时读不懂题，理解能力为 0。
用 dp 的思想，把每个区间按照左端点从小到大排序（方便后面前缀和统计），然后将区间一个个加入，依次统计答案。另 f[i] 表示选了 i 个区间时的总价值。
在状态转移时，f[i] 的取值来自两部分：一是前 i - 1 个区间子集产生的价值，这个不会因为加入新区间而改变；另一部分是来自于前 i - 1 个区间中和第 i 个区间没有交集的区间，它们的价值分别会加 1。设 x 表示和当前区间不相交的区间个数，由集合的性质得到这样的子集共有 $2^x$ 个。
于是得到 $f[i] = f[i - 1] + (f[i - 1] + 2^x)$。
接下来就是求 x。设当前区间为 i，与其不相交的区间为 j，则 $a[i].r < a[j].l$。于是我们统计一遍区间的所有右端点，对于每个位置进行一个前缀和表示这个位置之前有多少个区间，于是 $x = s[a[i].l - 1]$。这也是为什么要按照左端点排序。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n;
int ans;
int f[N], sum[N];
struct node{int l, r;}a[N];
bool cmp(node x, node y){return x.l < y.l;}
int bpow(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
signed main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++ )
{
scanf("%d%d", &a[i].l, &a[i].r);
s[a[i].r] ++;
}
for(int i = 1; i <= n * 2; i ++ ) s[i] += s[i - 1];
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i ++ ) f[i] = (f[i - 1] * 2 % mod + bpow(2, s[a[i].l - 1])) % mod;
printf("%d", f[n]);
return 0;
}
```