sb数据范围诈骗
神仙结论题。
双方不需要采取任何策略。
考虑枚举空位，限制是不能两两相邻。容斥+插板法即得：
答案是 ∑ i ≤ n 2 2 ( 2 ( n − i i ) − ( n − i − 1 i ) ) ( n − i ) ! \sum_{i\le \frac{n}{2}}2(2\binom{n-i}{i}-\binom{n-i-1}{i})(n-i)! ∑i≤2n2(2(in−i)−(in−i−1))(n−i)!
我会转化！！
我会分别计算行和列的方案数，然后乘起来！！
我会转化！！
考虑能放置 i i i个球的概率。
证明：不妨假设每次放的位置是递增的。那么每种局面的概率相等。
答案是 1 + ∑ i = 0 n k ( n − i k + i i + 1 ) ( n i + 1 ) 1+\sum_{i=0}^{\frac{n}{k}}\frac{\binom{n-ik+i}{i+1}}{\binom{n}{i+1}} 1+∑i=0kn(i+1n)(i+1n−ik+i)
我会转化！！
又来数据范围诈骗
合法的 G = ( V , E ) G=(V,E) G=(V,E)应该满足：
1.1
1.1
1.1对于任意
v
v
v存在唯一
(
u
,
v
)
(u,v)
(u,v)满足
d
[
u
]
+
1
=
d
[
v
]
d[u]+1=d[v]
d[u]+1=d[v]
1.2
1.2
1.2对于任意
(
u
,
v
)
(u,v)
(u,v)满足
∣
d
[
u
]
−
d
[
v
]
∣
≤
1
|d[u]-d[v]|\le 1
∣d[u]−d[v]∣≤1
考虑计数。设 g i , j , k g_{i,j,k} gi,j,k表示当前层有 i i i个点，前一层有 j j j个度为 2 2 2的点， k k k个度为 3 3 3的点，当前层和上一层的树边和上一层的非树边的方案数。 f i , j f_{i,j} fi,j表示 i i i所在层有 j j j个点方案数。
那么 f i , j = ∑ k = 1 i − j f i − j , k g j , c 0 , c 1 f_{i,j}=\sum_{k=1}^{i-j}f_{i-j,k}g_{j,c_0,c_1} fi,j=∑k=1i−jfi−j,kgj,c0,c1 ，答案是 ∑ i = 1 n f n , i g 0 , c 0 , c 1 \sum_{i=1}^nf_{n,i}g_{0,c_0,c_1} ∑i=1nfn,ig0,c0,c1 。
如果 i ≠ 0 i\ne 0 i=0那么优先考虑当前层和上一层的树边。
如果 i = 0 i=0 i=0, j = 0 j=0 j=0那么 g 0 , 0 , k = ( k − 1 2 ) g 0 , 2 , k − 3 g_{0,0,k}=\binom{k-1}{2}g_{0,2,k-3} g0,0,k=(2k−1)g0,2,k−3
如果 i = 0 , k = 0 i=0,k=0 i=0,k=0那么 g 0 , j , 0 = ( j − 1 ) ! ! g_{0,j,0}=(j-1)!! g0,j,0=(j−1)!!
如果 i = 0 i=0 i=0, j ≠ 0 j\ne 0 j=0, k ≠ 0 k\ne 0 k=0那么 g 0 , j , k = ( j − 1 ) g 0 , j − 2 , k + k g 0 , j , k − 1 g_{0,j,k}=(j-1)g_{0,j-2,k}+kg_{0,j,k-1} g0,j,k=(j−1)g0,j−2,k+kg0,j,k−1
复杂度 O ( n 3 ) O(n^3) O(n3)。
tips：转移的时机与策略
服了。
我会转化！！显然
问题转化为，对于一个初始为 1 ∼ n 1\sim n 1∼n的序列，每次将第 x i x_i xi个数插入到 k i k_i ki位置，求最终序列。
考虑其逆操作。注意到其逆操作插入的位置是单调的，也就是说每次会还原一段后缀，那么我们知道线段树二分出来的这个点是 x i x_i xi，并且将这个点删掉。这样我们就求到了每个 x i x_i xi在最终序列的位置。
设
t
o
t
tot
tot表示要求
a
i
<
a
i
+
1
a_i
我们把若干次翻折后的图形展开，那么得到 2 i × 2 j 2^i\times 2^j 2i×2j个小矩形，那么把每个小矩形从中间横着切一刀，竖着切一刀，就会得到 ( 2 i + 1 ) ( 2 j + 1 ) (2^i+1)(2^j+1) (2i+1)(2j+1)个块（中间的折痕是相连的）
答案是 ∑ i = 0 n ( n i ) ( 2 i + 1 ) ( 2 n − i + 1 ) 2 n = 2 n + 4 n + 2 × 3 n 2 n \frac{\sum_{i=0}^n\binom{n}{i}(2^i+1)(2^{n-i}+1)}{2^n}=\frac{2^n+4^n+2\times 3^n}{2^n} 2n∑i=0n(in)(2i+1)(2n−i+1)=2n2n+4n+2×3n
我会转化！！
设 s ( i , k ) s(i,k) s(i,k)表示 i i i个数选不超过 k k k个的方案数
那么
s
(
i
,
k
)
=
2
s
(
i
−
1
,
k
)
−
(
i
−
1
k
)
s(i,k)=2s(i-1,k)-\binom{i-1}{k}
s(i,k)=2s(i−1,k)−(ki−1) 组合意义nb
答案是 ∑ i = 1 n 1 0 i − 1 ( f ( n − i ) s ( n − 1 − i , k − 2 ) + a [ n − i + 1 ] s ( n − i , k − 1 ) ) \sum_{i=1}^{n}10^{i-1}(f(n-i)s(n-1-i,k-2)+a[n-i+1]s(n-i,k-1)) ∑i=1n10i−1(f(n−i)s(n−1−i,k−2)+a[n−i+1]s(n−i,k−1))
复杂度 O ( ∑ n ) O(\sum n) O(∑n)