• https://codeforces.com/contest/1750

Problem D. Count GCD

似乎是 隔壁原题…

Problem E. Bracket Cost

• https://zhuanlan.zhihu.com/p/581182890

没做出来似乎是因为 读错了题…

给定一个括号序列，问所有子序列的平衡代价 f() 的和。 f() 定义为，用最少的 shift 和 insert 操作，使该序列平衡。
注意 shift 操作可以任选一个子串进行…

Problem F. Majority

问有多少长度位 n (n<=5000) 的 0-1 序列，满足该序列可以执行任意次连接操作变为全 1. 连接操作定义为，选择一个区间 i,j, 满足 si = sj = 1，将 [i,j] 全部变为 1，要求操作前区间中 1 的数目 >= 0 的数目。

dp[i][j] 表示最终状态长度为 i，且左边有连续 j 个 1（形如 111100..001）的方案数。

Problem G. Doping

先不考虑字典序的问题，那么是某种对排列的划分。。。
这类题目有很多，比如 [Shoi2007] Permutation 有序的计数..（这两个题目还确实挺有关联的。。。）
需要先 dp 出这个东西，然后考虑字典序只要枚举前缀即可。

错位排列
https://en.wikipedia.org/wiki/Derangement
http://oeis.org/A000166

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, ...

k 不动点排列
https://en.wikipedia.org/wiki/Rencontres_numbers

1                               
0   1                           
1   0   1                       
2   3   0   1                   
9   8   6   0   1               
44  45  20  10  0   1           
265 264 135 40  15  0   1       
1854    1855    924 315 70  21  0   1   
14833   14832   7420    2464    630 112 28  0   1

http://oeis.org/A134830
第一个不动点在位置 k 的排列
（有 k 个对象有后继的排列，使得排列中没有连续数字）

1
1 0
2 1 1
6 4 3 2
24 18 14 11 9
120 96 78 64 53 44
720 600 504 426 362 309 265
5040 4320 3720 3216 2790 2428 2119 1854
40320 35280 30960 27240 24024 21234 18806 16687 14833
362880 322560 287280 256320 229080 205056 183822 165016 148329 133496
414233 51353 2943360 2656080 2399760 2170680 1965624 1781802 1616786 1468457 1334961

能被分成 k 段的排列（每段都是连续数字）

0
1 0
1 2 2
1 3 9 10
1 4 18 44 52
1 5 30 110 265 308
1 6 45 220 795 1854 2118
1 7 63 385 1855 6489 14833 16686
1 8 84 616 3710 17304 59332 133496 148328
1 9 108 924 6678 38934 177996 600732 1334961 1468456

最长连续段长度为 k 的排列？

环的数目
http://oeis.org/A008275

1
1 1
2 3 1
6 11 6 1
24 50 35 10 1
120 274 225 85 15 1
720 1764 1624 735 175 21 1
5040 13068 13132 6769 1960 322 28 1
40320 109584 118124 67284 22449 4536 546 36 1
362880 1026576 1172700 723680 269325 63273 9450 870 45 1

最长环
http://oeis.org/A126074

1
1 1
1 3 2
1 9 8 6
1 25 40 30 24
1 75 200 180 144 120
1 231 980 1260 1008 840 720
1 763 5152 8820 8064 6720 5760 5040
1 2619 28448 61236 72576 60480 51840 45360 40320
1 9495 162080 461160 653184 604800 518400 453600 403200 362880

最短环
http://oeis.org/A145877

1
1 1
4 0 2
15 3 0 6
76 20 0 0 24
455 105 40 0 0 120
3186 714 420 0 0 0 720
25487 5845 2688 1260 0 0 0 5040
229384 52632 22400 18144 0 0 0 0 40320
2293839 525105 223200 151200 72576 0 0 0 0 362880

Problem H. BinaryStringForces

也是 0-1 序列，任意执行操作，这里首先把序列按照连续的 01 分成若干端，每次操作定义为选择相邻的两段，将较少的颜色染成较多的（相等时染色成 1）。
问给定的长度为 n 的字符串，有多少子串，满足可以执行任意次操作后全部染色成 1。