来自qrsikno的课件

AGC002F Leftmost Ball

Description

给定 nn 种颜色, 每种颜色有 kk 个球.

现在把他们排列成一行, 再把每种颜色第一个染成 0 号颜色 (之前未出现).

求经过操作之后能有多少种不同的序列.

两个序列不同被认为是长度不同或某个位置颜色不同.

n2000,k2000n \le 2000, k \le 2000

Solution

因为颜色等价,可以忽略颜色的排列顺序,最后乘上k!k!

00和其他颜色放一起填,需要保证任意前缀都有num0numcolornum_0 \ge num_{color}

dp[i][j]dp[i][j]表示当前填了ii00jj种颜色的方案数,每次把一种颜色全部加进来

dp[i][j]=dp[i1][j]+dp[i][j1]×(nki(j1)(k1)1k2) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\times \binom{nk - i - (j - 1)(k - 1) - 1}{k - 2}

dp[i1][j]dp[i - 1][j]的系数为11是因为必须钦定00放在当前第一个空位,否则会算重

组合数上面最后一项1-1同理,钦定第一个数填在第一个空位上

下面2-2是要减去00和当前颜色的第一个数

Luogu P1758 [NOI2009]管道取珠

Solution

ai2\sum a_i ^ 2可以看成两个完全一样的游戏同时进行,它们得到了相同的串的方案数

dp[i][j][k][l]dp[i][j][k][l]表示第一个游戏进行到(i,j)(i, j),第二个进行到(k,l)(k, l)的方案数

显然l=i+jkl = i + j - k,复杂度O(n3)O(n^3)

CF1111D Destory the Colony

Description

给定一个偶数长度 n(n105)n(n \le 10^5 ) 的字符串, 只包含大小写字母.

q(q105)q(q \le 10^5 ) 次询问, 每次指定两个位置, 要求通过交换字符, 使这两个位置上的类型的字符在字符串中线同一边(要么全在左半边,要么全在右半边).

并且对于其他类型的字符, 不能跨过串的中线 (也就是说必须在一边, 但是可以不跟指定的字符一边).

询问之间独立, 求方案数模 109+710^9 + 7 的值

Solution

先不考虑指定的两个位置的限制

枚举SS表示放在左半边的字符的集合

根据可重排列计数,SS的答案就是:

(n2!)2iScntiiScnti=(n2!)2icnti \frac{(\frac{n}{2}!)^2}{\prod_{i\in {S}}cnt_i * \prod_{i\notin {S}}cnt_i} = \frac{(\frac{n}{2}!)^2}{\prod_i cnt_i}

发现与SS具体是什么无关

因为有S=n2|S| = \frac{n}{2},所以需要做一次背包求出方案数,再乘上面那个东西就是答案


然后考虑指定了位置(i,j)(i, j)怎么做

可能的(i,j)(i, j)很少,可以把答案都预处理

显然,只需要把iijj在背包中挖掉即可

1
2
for (int k = Cnt[i]; k <= N / 2; ++k)
Add (f[k], Mod - f[k - Cnt[i]]);

并且答案要乘22,因为iijj可以同时在左半边或者右半边

CF785D Anton and School 2

Description

19-8-6-1

Solution

19-8-6-2a