6.5
P3214 [HNOI2011] 卡农
设 \(f_i\) 表示选了 \(m\) 个集合的答案，简单观察发现，只要确定了 \(m-1\) 个集合，最后一个集合就是确定的，不是偶数次数的出现，偶数次数的不出现，选 \(m\) 个集合有 \(C_{2^n-1}^{m-1}\) 种方案，考虑下面两种不合法的情况。
- 这 \(m-1\) 个集合已经合法，最后一个集合为空集。
- 最后要选的集合在前面 \(m-1\) 个集合出现过。
答案就是总数减去这两种情况，第一种情况显然为 \(f_{i-1}\)，第二种情况其实就是有 \(i-2\) 个集合已经合法了，数量为 \(f_{i-2}\)，但是因为最后的一个集合（相同的两个）不确定，所以第二种情况实际上有 \(f_{i-2}\cdot[2^{n}-1-(i-2)]\)，直接减去就可以，这时因为我们每一种都算了 \(m\) 遍，所以答案要除以 \(m\)。
\[f_i=\frac{C_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}\cdot (2^n-i+1)}{m} \]直接递推即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
inline int read(){
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
const int N=1e6+10,mod=1e8+7;
inline int mo(int x){return x<0?(x%mod+mod)%mod:(x>=mod?x%mod:x);}
inline int qpow(int a,int b){
int res=1;
for(;b;b>>=1,a=mo(a*a))if(b&1)res=mo(res*a);
return res;
}
int n,m,sum,inv[N],C,f[N];
signed main(){
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
n=read(),m=read();sum=mo(qpow(2,n)-1);
if(m>sum){std::cout<<0<<'\n';exit(0);}
inv[1]=1,f[1]=f[2]=0;f[0]=1;
for(int i=2;i<=m;++i)inv[i]=mo((mod-mod/i)*inv[mod%i]);
C=mo(mo(sum*(sum-1))*inv[2]);
for(int i=3;i<=m;++i){
f[i]=mo(mo((C-f[i-1]-mo(f[i-2]*mo(sum-i+2))))*inv[i]);
C=mo(mo(C*(sum-i+1))*inv[i]);
}
std::cout<<f[m]<<'\n';
}
6.9
困困困，头疼疼疼疼疼，给大家来场 ABC 速通。
- A 直接扫
- B 直接扫
- C 递归周围，然后中间填白色
- D 设 \(len\) 为数字 \(n\) 十进制下的长度，\(V_n=n\cdot\sum_{i=0}^{n-1} 10^{i\cdot len}\)，后面直接等比数列求和 \(ans=n\cdot\frac{10^{n\cdot len}-1}{10^{len}-1}\)。
- E 就是求有向图每个点能到达的点（包括自己）的和，反向建边后直接缩点拓扑排序跑 DP 即可。
- F 一眼线段树，赛时傻逼没推下式子锅了，\((a+x)\cdot (b+y)=ab+xb+ya+xy\)，记两个 tag 即可。
- G 高级东西，不会。
6.15 ABC358 速通
D 直接二分找，然后删。
E 就是求多重集排列数，直接设 \(f_{i,j}\) 表示考虑前 \(i\) 个字母，长度为 \(j\) 时的方案数，枚举新加入多少个元素，有 \(f_{i,j}=\sum_{k=\max(0,j-c_i)}^{j}f_{i-1,j}\cdot C_j^k\)，最后 \(ans=\sum_{i=1}^{n}f_{26,i}\)
F 随便找，然后比较傻逼，没意思。
G 直接设状态 \(f_{t,i,j}\) 表示 \(t\) 时刻在 \((i,j)\) 的最大价值，转移就直接从 \(5\) 个位置转移，发现 \(k\) 很大，但是当 \(k\ge nm\) 时就没啥意义了，因为此时的最优解一定不会再从其他点转移了，所以考虑 \(k\le nm\) 时的答案，最后加上剩下的次数乘上价值找最大就行。