4.数学
数学1（容斥、组合数学、期望）
开题顺序： \(H\)
\(A\) CF1613F Tree Coloring
\(B\) CF1466H Finding satisfactory solutions
\(C\) Gym103415K Magus Night
\(D\) luogu P8292 [省选联考 2022] 卡牌
\(E\) CF1139D Steps to One
\(F\) CF908D New Year and Arbitrary Arrangement
\(G\) CF749E Inversions After Shuffle
\(H\) CF932E Team Work
-
猜测 \(\sum\limits_{i=1}^{n}\dbinom{n}{i}i^{k}\) 对 \(n,k\) 是可以递推的。
-
设 \(f_{n,k}=\sum\limits_{i=1}^{n}\dbinom{n}{i}i^{k}\) ，然后考虑把 \(\dbinom{n}{i}\) 拆成 \(\dbinom{n-1}{i}+\dbinom{n-1}{i-1}\) 。
-
推式子，有 \(\begin{aligned} f_{n,k} &=\sum\limits_{i=1}^{n}\dbinom{n}{i}i^{k} \\ &=\sum\limits_{i=1}^{n}\dbinom{n-1}{i-1}i^{k}+\sum\limits_{i=1}^{n}\dbinom{n-1}{i}i^{k} \\ &=\sum\limits_{i=1}^{n}\frac{i}{n}\dbinom{n}{i}i^{k}+\sum\limits_{i=1}^{n-1}\dbinom{n-1}{i}i^{k} \\ &=\frac{1}{n}\sum\limits_{i=1}^{n}\dbinom{n}{i}i^{k+1}+f_{n-1,k} \\ &=\frac{1}{n}f_{n,k+1}+f_{n-1,k} \end{aligned}\) 。
-
移项得到 \(f_{n,k+1}=n(f_{n,k}-f_{n-1,k})\) ，用 \(k\) 代替 \(k+1\) 得到 \(f_{n,k}=n(f_{n,k-1}-f_{n-1,k-1})\) 。
-
因为 \(k \le 5000\) ，分讨 \(n,k\) 的大小关系后类似阶梯状向下更新即可。边界为 \(\begin{cases} f_{n',0}=\sum\limits_{i=1}^{n'}\dbinom{n'}{i}=2^{n'}-1 & n' \in [1,n] \\ f_{1,k'}=1 & k' \in [0,k] \end{cases}\) 。
点击查看代码
const ll p=1000000007; ll f[2][5010]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { ll n,k,i,j; cin>>n>>k; if(n<k) { for(i=0;i<=k;i++) { f[1][i]=1; } for(i=2;i<=n;i++) { f[i&1][0]=(qpow(2,i,p)-1+p)%p; for(j=1;j<=k;j++) { f[i&1][j]=(f[i&1][j-1]-f[(i-1)&1][j-1]+p)%p*i%p; } } } else { f[(n-k)&1][0]=(qpow(2,n-k,p)-1+p)%p; for(i=n-k+1;i<=n;i++) { f[i&1][0]=(qpow(2,i,p)-1+p)%p; for(j=1;j<=k;j++) { f[i&1][j]=(f[i&1][j-1]-f[(i-1)&1][j-1]+p)%p*i%p; } } } cout<<f[n&1][k]<<endl; return 0; }
\(I\) CF578D LCS Again
\(J\) luogu P7914 [CSP-S 2021] 括号序列
\(K\) luogu P8340 [AHOI2022] 山河重整
数学2（同余、计算几何、线性代数）
开题顺序： \(A\)
\(A\) luogu P3306 [SDOI2013] 随机数生成器
- 多倍经验: [ABC270G] Sequence in mod P | Gym103486C Random Number Generator
- 题解
\(B\) luogu P3194 [HNOI2008] 水平可见直线
\(C\) luogu P4049 [JSOI2007] 合金
\(D\) luogu P9181 [COCI2022-2023#5] Zastave
\(E\) luogu P8885 「JEOI-R1」子序列
\(F\) luogu P7116 [NOIP2020] 微信步数
\(G\) CF963E Circles of Waiting
\(H\) CF1815E Bosco and Particle
\(I\) CF1067E Random Forest Rank
版权声明：本作品采用 「署名-非商业性使用-相同方式共享 4.0 国际」许可协议（CC BY-NC-SA 4.0） 进行许可。