Ta:排列有乱序下的唯一限制,转换为了组合
如果没有不超过n的话,你还要去特判第一个做不做成0
但是他说不超过,就可以是做有前导0
然后可重集组合,可不选一种
先看每种都必须选的,相当于隔板法, $C_{n-1}^{m-1}$
然后可不选?每种都预分配,$ C_{n+m-1}^{m-1} $
Tb:本题复习经典棋盘容斥
f[i]–>到达i个障碍的时候前面都没有障碍的方案数
g(n,m)–>poi (0,0)–>(n,m)无论怎么走的方案数
本题= $ C_(n+m)^{n} $
但是如果可以斜着走:去枚举斜着走的边有哪些
斜着走一次相当于额外少一个横/竖的方案
$ C_{n+m-i}^{i} $
然后还剩下 $(n+m-i-i)$ 步给横和竖,还要横着走 $i$
$C_{n+m-i-i}^{n-i} $
最后就是f[i]=(到i的方案无论怎么走)-f[j]*(j到i的方案无论怎么走)
然后对于过河卒:发现它模数很小要求很大,考虑 $lucas$
复习: $ lucas $–>
$ C_n^m \bmod p $
= $ C_{n \bmod p}^{ m \bmod p }\times $
$ C_{n / p}^{ m / p } $
C:为了和更小,他肯定先走1走一半再折下去
折下去?
组合恒等式,over
D.扩展lucas,现在还没过,受不了了
E.分解模数,分成4个质数,然后对着每个模数求个答案,最后crt合并就好,局部的话就枚举因数算lucas,
选苹果:
观察到,记 $ F_i^j$
$= \sum_{j=0}^{i} C_i^j$
其中$ F_i^{j+1}=F_i^j+C_i^{j+1} $
$ F_{i+1}^j=F_i^j*2+C_{i+1}^j $
前后项可O(1)转移,考虑下面左端点,上面右端点,跑莫队
精妙!
集合划分:dp,f[i][j]–>前i个,划分为j个集合的方案书
$f[i][j]=f[i-1][j]*j+f[i-1][j-1]$,分讨这个点开不开集合,进哪个集合就行
自然数拆分:根分dp
转移1:$f[i][j]=f[i][j-1]+f[i-j][j]$,第二维表示最大用
转移2:$g[i][j]=g[i-j][j]+g[i-1][j-1]$,第二维表示个数
注意到第一个方程门槛在最大用多少,第二个方程门槛在至少用多少
根分over
最后Σg,Σf,枚举他们分别承担多少和的任务,组内相乘组外相加,over
注意可以全部用全部小于根号的,特盘over
k.容斥,枚举不取几个值
ans=总情况-1个取不到+2个取不到-3个取不到…
eg:1个取不到? $ C_m^1 \times (m-i)^n *(-1)$
n个点,每个店都有m-i种选法
L:房间内放另一个房间的钥匙,可以看成一个置换,即有向环
m次机会?等价于n个点形成的环数不超过m
$Σ_j=1^m f[n][j]$?
第一类string
why?他可以插入前面任何一个元素的左边,都可以构成新的圆排
完了吗?第一个点无法破坏等价于第一个点不成自环
去看看它的钥匙放的哪一个房间的就好了
假设[p1,p2],p1放p2的,那么现在p1放1的,1放p2的,精妙的构造!
那么 $\sum f[n-1][m]*(n-1)$