11.1
CF449D Jzzhu and Numbers
题目分析：
考虑直接算的话就相当于限制每一位必须有一个 \(0\)，显然不如反着来，也就是某一位必须全为 \(1\)，也就是我们计算与之后不为 \(0\) 的方案，用总的方案数也就是 \(2^n\) 减一下就好了。
我们可以观察到数据范围里很怪的一点：\(a_i \le 10^6\)，这也就提示我们可以按位来考虑。
具体来说就是可以设 \(dp[S]\) 表示我们选择含有 \(S\) 这些 \(1\) 的数的个数，严谨一点就是求解 \(\sum_{i=1}^n [a_i \& S = S]\)，这显然可以每个数对它对应的数做贡献，然后做一遍高维后缀和就好了。
我们最终的答案难道就是所有的 \(S\) 求个和嘛？显然不是啊。
因为我们要求的其实是第一位为 \(1\) 或 第二位为 \(1\) 或 \(\cdots\)。
发现可以容斥啊，其实就是 \(S\) 中含有奇数个 \(1\) 的加上，含有偶数个 \(1\) 的减去，然后就结束了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
int f[1<<22],a[N],pre[N];
int mod(int x){
return ((x % MOD)+MOD)%MOD;
}
signed main(){
int n;
scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]),f[a[i]]++;
for(int j=0; j<20; j++){ //高维后缀和
for(int i=1; i<(1<<20); i++)
if((i >> j) & 1){
f[i ^ (1<<j)] = mod(f[i ^ (1<<j)] + f[i]);
}
}
pre[0] = 1;
for(int i=1; i<=n; i++) pre[i] = mod(pre[i-1] * 2); //pre[i] = 2^i，方便计算答案
int ans = pre[n] - 1; //因为必须选择一个，所有去掉全部不选的情况
for(int i=1; i<(1<<20); i++){
int cnt = __builtin_popcount(i);
if(cnt & 1) ans = mod(ans - (pre[f[i]] - 1)); //因为是求的 ans - 方案数，所以奇数是减
else ans = mod(ans + (pre[f[i]] - 1));
}
printf("%lld\n",ans);
return 0;
}
CF932E Team Work
题目分析：
先稍微说一下第二类斯特林数吧。
第二类斯特林数就是 \(S_n^m\) 表示将 \(n\) 个不同的小球放到 \(m\) 个相同的盒子里的方案数，也可以记作 \(\begin{Bmatrix} n \\ m\end{Bmatrix}\)
递推式的就是 \(\begin{Bmatrix} n \\ m \end{Bmatrix} = \begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix} + m \times \begin{Bmatrix} n-1 \\ m \end{Bmatrix}\)，其实就是可以理解为枚举最后一个小球是否单独开一个盒子，不单独开的式子是因为小球是不同的所以放到不同的盒子算作不同的方案所以要乘以 \(m\)。
下面其实才是常用的点，一个性质：
感觉本题的推导也很有用，包含了很多技巧。
\[\begin{aligned} &\sum_{i=1}^n \binom{n}{i} \times i^k \\ &= \sum_{i=0}^n \binom{n}{i} \times i^k \\ &= \sum_{i=0}^n \dfrac{n!}{i!(n-i)!} \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} \times \binom{i}{j} \times j! \\ &= \sum_{i=0}^n \dfrac{n!}{(n - i)!} \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} \times \dfrac{1}{(i-j)!} \\ &= \sum_{i=0}^n \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} \dfrac{n!}{(n-i)!(i-j)!} \\ &= \sum_{i=0}^n \begin{Bmatrix} k \\ j \end{Bmatrix} \sum_{i=0}^n \dfrac{(n-j)!}{(n-i)!(i-j)!} \times \dfrac{n!}{(n - j)!} \\ &= \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} \dfrac{n!}{(n-j)!} \sum_{i=0}^n \binom{n-j}{n-i} \\ &= \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} \dfrac{n!}{(n-j)!}2^{n-j} \end{aligned} \]然后直接预处理一下第二类斯特林数就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 5005;
int S[N][N];
int mod(int x){
return x % MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
void pre_work(int mx){
S[0][0] = 1;
for(int i=1; i<=mx; i++){
for(int j=1; j<=i; j++){
S[i][j] = mod(S[i-1][j-1] + mod(j * S[i-1][j]));
}
}
}
signed main(){
int n,k;
scanf("%lld%lld",&n,&k);
pre_work(k);
int ans = 0,tmp1 = 1,tmp2 = power(2,n),inv2 = power(2,MOD-2);
for(int i=0; i<=k; i++){
ans = mod(ans + mod(mod(S[k][i] * tmp1) * tmp2));
tmp1 = mod(tmp1 * (n - i));
tmp2 = mod(tmp2 * inv2);
}
printf("%lld\n",ans);
return 0;
}
CF1485F Copy or Prefix Sum
题目分析：
注意我们是给定 \(b\) 填 \(a\) 别被绕晕了。
我们考虑假设我们已经填完到了第 \(i\) 位且前 \(i-1\) 位和为 \(S\)，那么我们这一位可以填什么。
显然只有两个值对应两种性质：\(b_i、b_i - S\)。
那么我们就可以考虑设 \(dp[i]\) 表示和为 \(i\) 的方案，省略第一维前多少位。
那么转移就是：
第一个转移就相当于一个偏移，第二个转移就相当于一个加全局和，都是很好弄的。
但是需要注意当上面的两个值相等，也就是 \(S = 0\) 时，一个转移就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
int a[N];
signed main(){
int t;
scanf("%lld",&t);
while(t--){
int n;
scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
map<int,int> f;
int ans = 1,sum = 0; //记录偏移量
f[0] = 1;
for(int i=1; i<=n; i++){
int tmp = f[sum];f[sum] = ans;sum -= a[i];
ans = ((ans + ans - tmp)%MOD+MOD)%MOD;
}
printf("%lld\n",ans);
}
return 0;
}
11.2
CF1628D2 Game on Sum (Hard Version)
题目分析：
显然可以考虑设 \(dp[i][j]\) 表示前 \(i\) 次操作 \(Bob\) 选择了 \(b\) 次加的最终的答案。
那么假设 \(Alice\) 选择 \(t\) 的话，转移方程就是：
可以发现我们睿智的 \(Alice\) 一定会选择 \(t = \dfrac{dp[i-1][j] + dp[i-1][j-1]}{2}\)，可以证明如果比这个值大或者比这个值小都不是最优的。
\(dp\) 初值就显然是 \(dp[i][i] = i \times k,dp[i][0] = 0\)。
我们考虑对于这个式子其实就相当于 \(dp[i][j]\) 会对 \(dp[i+1][j]\) 和 \(dp[i+1][j+1]\) 产生 \(\dfrac{dp[i][j]}{2}\) 的贡献，那么就考虑每一个 \(dp[i][i]\) 对 \(dp[n][m]\) 的贡献就好了，显然 \(Bob\) 最多会选择 \(m\) 次加。
我们考虑转化一下其实就是相当于从 \((i,i)\) 走到 \((n,m)\) 的方案数就是它的贡献次数，但是从 \((i,i)\) 走到 \((i+1,i+1)\) 是显然没有意义的，因为 \((i+1,i+1)\) 就是一个初值，所以就是可以理解为从 \((i+1,i)\) 走到 \((n,m)\) 的方案数，其实就是 \(n - i - 1\) 步里选 \(m-i\) 步向上，就是 \(\binom{n-i-1}{m-i}\)，但是我们每一步都会造成贡献除二，显然我们总共走了 \(n-i\) 步，因为我们第一次走的也算一步，所以答案也要除以 \(2^{n-i}\)，所以最终就是：
那么直接暴力算这个式子的值就好了。
但是需要特判 \(n=m\) 的情况，因为我们把这个当作了初值，所以不会去处理。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
int fac[N],inv[N],pw[N];
int mod(int x){
return x % MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
void pre(int mx){
fac[0] = 1;
for(int i=1; i<=mx; i++) fac[i] = mod(fac[i-1] * i);
inv[mx] = power(fac[mx],MOD-2);
for(int i=mx-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i + 1));
int inv2 = power(2,MOD-2);
pw[0] = 1;
for(int i=1; i<=mx; i++) pw[i] = mod(pw[i-1] * inv2);
}
int C(int n,int m){
if(n < m) return 0;
return mod(mod(fac[n] * inv[m]) * inv[n - m]);
}
signed main(){
pre(1000000);
int t;
scanf("%lld",&t);
while(t--){
int n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
int ans = 0;
for(int i=1; i<=m; i++){
ans = mod(ans + mod(mod(mod(k * i) * C(n-i-1,m-i)) * pw[n-i]));
}
if(n == m) ans = mod(k * m);
printf("%lld\n",ans);
}
return 0;
}
CF1499E Chaotic Merge
题目分析：
我们发现如果我们要求的是整个字符串的答案的话可以轻松地 \(dp\) 解决。
也就是设 \(dp[i][j][0/1]\) 表示使用了 \(x\) 的前 \(i\) 个和 \(y\) 的前 \(j\) 个，最后一个选择的是 \(y\) 或 \(x\) 的合法方案数。
这样可以根据 \(dp\) 值就很轻松地将右端点的问题解决了，但是左端点的移动怎么办呢？
我们会发现对于不同的左端点其对于 \(dp\) 值的影响只在于初值，所以我们对于每一个位置都赋一个初值然后去 \(dp\) 就好了。
但是这样又出现了一个问题，对于题目中式子的一个隐藏条件：\(|x|,|y| \ge 1\)，所以这样之后会发生对于 \(i\) 他可能是 \(j\) 来说合法的右端点但不一定是 \(k\) 来说合法的右端点，所以直接对 \(dp\) 值求和就会出问题，因为会发现 \(|x| = 0\) 或 \(|y| = 0\) 的情况。
我们就考虑再记一维这一维是一个二进制状态第一位代表是否选择过 \(x\)，第二位代表是否选择过 \(y\)，这样统计就很简单了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3+5;
const int MOD = 998244353;
char x[N],y[N];
int dp[N][N][2][4];
void add(int &x,int y){
x = (x + y)%MOD;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%s%s",x+1,y+1);
int n = strlen(x+1);
int m = strlen(y+1);
for(int i=0; i<=n; i++){
for(int j=0; j<=m; j++){
if(i < n) add(dp[i+1][j][1][1],1);
if(j < m) add(dp[i][j+1][0][2],1);
for(int s=0; s<4; s++){
if(i < n && x[i+1] != x[i]) add(dp[i+1][j][1][s | 1],dp[i][j][1][s]);
if(j < m && y[j+1] != x[i]) add(dp[i][j+1][0][s | 2],dp[i][j][1][s]);
if(i < n && x[i+1] != y[j]) add(dp[i+1][j][1][s | 1],dp[i][j][0][s]);
if(j < m && y[j+1] != y[j]) add(dp[i][j+1][0][s | 2],dp[i][j][0][s]);
}
}
}
int ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
add(ans,dp[i][j][0][3] + dp[i][j][1][3]);
}
}
printf("%lld\n",ans);
return 0;
}
CF1109D Sasha and Interesting Fact from Graph Theory
题目分析：
我们可以考虑拆分问题，把问题看作两个步骤：
- 构造出 \(a,b\) 间的路径
- 将其他点挂到这个路径上，形成一棵树
对于这个数据范围显然可以考虑直接枚举链上点的个数，设为 \(i\)，那么对于选择路径的方案数就是 \(\binom{n-2}{i-2} \times (i-2)! \times \binom{m-1}{i-2}\)。
具体解释一下：因为 \(a,b\) 必选，所以我们可以操作的点其实就少了两个，因为 \(i-2\) 个点可以任意排列且不同的排列属于不同的方案所以要乘以一个阶乘，然后最后就是将 \(m\) 的权值分给 \(i-1\) 条边，经典的插板法应用。
然后把其余的点挂到路径上就是广义 Cayley 定理啦，也就是 \(i \times n^{n - i - 1}\)
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
int fac[N],inv[N];
int mod(int x){
return x % MOD;
}
int power(int a,int b){
b = (b + MOD-1)%(MOD-1); //会离谱的出现负数，所以就考虑欧拉定理
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
void pre_work(int mx){
fac[0] = 1;
for(int i=1; i<=mx; i++) fac[i] = mod(fac[i-1] * i);
inv[mx] = power(fac[mx],MOD-2);
for(int i=mx-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i + 1));
}
int C(int n,int m){
if(n < m) return 0;
return mod(fac[n] * mod(inv[m] * inv[n-m]));
}
signed main(){
pre_work(1000000);
int n,m; //a,b 形如空谈
scanf("%lld%lld",&n,&m);
int ans = 0;
for(int i=2; i<=min(n,m+1); i++){ //枚举链上有多少个点，显然最多就是 m + 1 了。
int P1 = mod(i * power(n,n - i - 1)); //把剩下的点挂到链上
int P2 = C(m-1,i-2); //把权值 m 分配到 i-1 条边上
int P3 = fac[i-2]; //这几个点可以任意排列
int P4 = C(n-2,i-2); //这几个点可以任选
int P5 = power(m,n - i); //剩下的边的权值可以随意赋
ans = mod(ans + mod(P1 * mod(P2 * mod(P3 * mod(P4 * P5)))));
}
printf("%lld\n",ans);
return 0;
}
11.3
CF856C Eleventh Birthday
题目分析：
显然可以发现一点，题目中的条件可以转化为偶数位上的数与奇数位上的数大小相同。
我们可以发现对于奇数位和偶数位的数对于答案的影响是不同的，所以可以考虑分开处理。
可以考虑设 \(f[i][j][k]\) 表示前 \(i\) 个奇数位的数，有 \(j\) 个的开头在偶数位上，对结果的贡献为 \(k\) 的方案数。
注意：这里的方案数只是指的我们顺次安排偶数位的结果，对于剩下的一些奇数位可能是空余的，不过不要紧。
也同理可以设 \(g[i][j][k]\) 表示前 \(i\) 个偶数位的数，有 \(j\) 个的开头在偶数位上，对结果的贡献为 \(k\) 的方案数。
转移其实就很简单了，就是枚举当前这个数在偶数位还是奇数位，我们记 \(a[i]\) 代表第 \(i\) 个奇数位的数对答案的贡献，\(b[i]\) 代表第 \(i\) 个偶数位的数对答案的贡献：
也可以显然发现一点，这样转移出来对于 \(f\) 来说，有用的只有 \(f[n][n/2][\cdots]\)，我们这里记 \(n\) 为奇数位的数的个数，\(m\) 为偶数位的数的个数。
那么我们接下来就可以考虑将这两个数组合并，可以考虑枚举偶数位 \(i\) 个数位于偶数位上对答案的贡献为 \(j\)，那么我们的方案数就是：
但是这个只是我们选数的方案啊，我们还需要考虑数与数之间的插入，可以发现因为任意插入偶数位的数不会改变原来存在的数的贡献，所以就可以考虑将偶数位的数插入奇数位的数内。
对于偶数位的数的这 \(i\) 个，必须位于奇数位的这 \(n - \dfrac{n}{2}\) 个数后面，而且一个数后面可以含有多个或者一个都没有，其实就是一个插板法啊。
也同理对于偶数位的剩下的 \(m-i\) 个数，必须位于奇数位的这 \(n/2\) 个数后面，也是一个插板法。
但是这个是显然不够的，因为我们会发现对于偶数位的数我们将开头在偶数位的数任意交换位置之后都是合法的且全新的一种方案，对于开头在奇数位的同理。而对于奇数位的数这个条件显然也满足，所以答案要乘以一个：
\[i! \times (m - i)! \times (\lfloor \dfrac{n}{2} \rfloor)! \times (n - \lfloor \dfrac{n}{2} \rfloor)! \]虽然说了这么多，但是其实代码是很好写的。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4005;
int f[2][N][12],g[2][N][12],fac[N],C[N][N],a[N],b[N];
int mod(int x,int MOD){
return ((x % MOD)+MOD)%MOD;
}
void Add(int &x,int y){
x = (x + y) % 998244353;
}
int calc(int n,int m){
if(m == 0) return n == 0;
return C[n + m - 1][m - 1];
}
int get(int x){
if(x == 0) return 1;
int cnt = 0;
while(x){
cnt++;
x/=10;
}
return cnt;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
scanf("%lld",&t);
fac[0] = 1;
for(int i=1; i<=2000; i++) fac[i] = mod(fac[i-1] * i,998244353);
C[0][0] = 1;
for(int i=1; i<=2000; i++){
C[i][0] = 1;
for(int j=1; j<=i; j++){
C[i][j] = mod(C[i-1][j] + C[i-1][j-1],998244353);
}
}
while(t--){
//奇数：奇数位的数 偶数：偶数位的数
int p;
int n = 0,m = 0;
scanf("%lld",&p);
for(int i=1; i<=p; i++){
int h;scanf("%lld",&h);
if(get(h) & 1) a[++n] = h % 11;
else b[++m] = h % 11;
}
//设 f[i][j][k] 表示前 i 个为奇数的数，有 j 个的开头在偶数位上，贡献为 k 的方案数
//g 就是将第一个改为了前 i 个为偶数的数
//这里是强制为每一个数选定一个他是偶数位/奇数位，具体是否合法也不一定呢
f[0][0][0] = 1;
for(int i=1; i<=n; i++){
int now = i & 1;
memset(f[now],0,sizeof(f[now]));
for(int j=0; j<=i; j++){
for(int k=0; k<=10; k++){
Add(f[now][j][k],f[now^1][j][mod(k - a[i],11)]);
if(j) Add(f[now][j][k],f[now^1][j-1][mod(k + a[i],11)]);
}
}
}
g[0][0][0] = 1;
for(int i=1; i<=m; i++){
int now = i & 1;
memset(g[now],0,sizeof(g[now]));
for(int j=0; j<=i; j++){
for(int k=0; k<=10; k++){
Add(g[now][j][k],g[now^1][j][mod(k - b[i],11)]);
if(j) Add(g[now][j][k],g[now^1][j-1][mod(k + b[i],11)]);
}
}
}
int ans = 0;
for(int i=0; i<=m; i++){ //枚举偶数有多少个在偶数位上。
for(int j=0; j<=10; j++){ //枚举偶数的贡献
Add(ans,g[m&1][i][j] * f[n&1][n/2][mod(11 - j,11)] %998244353 * fac[i] %998244353* fac[m - i] %998244353* fac[n/2] %998244353* fac[n - (n / 2)] %998244353* calc(m - i,n / 2 + 1) %998244353* calc(i,n - (n / 2)));
//m - i 个数必须放在 n/2 这些数对应的后面或第一个数前面，也就是插板法，可以为空
}
}
printf("%lld\n",ans);
for(int i=0; i<=n+1; i++) for(int j=0; j<=10; j++)f[1][i][j] = f[0][i][j] = 0;
for(int i=0; i<=m+1; i++) for(int j=0; j<=10; j++)g[1][i][j] = g[0][i][j] = 0;
}
return 0;
}
11.5
CF946F Fibonacci String Subsequences
题目分析：
可以发现，我们其实可以使用合并的思想去看这个题，就是啥意思呢。
我们在 \(F(i)\) 内的方案数，其实就是在 \(F(i-1)\) 里的方案数加在 \(F(i-2)\) 里的方案数加横跨 \(F(i-1)\) 和 \(F(i-2)\) 的方案数。
就考虑怎么做可以做到处理横跨的这种情况。
显然可以想到一个 \(dp\)，就是设 \(f[i][j][k]\) 表示在 \(F(i)\) 中 \([j,k]\) 这个子串作为其某一个子序列的子串的次数。
讨论转移也是上面这个想法。
考虑全在 \(F(i-1)\) 中的怎么算，直接就是 \(f[i-1][j][k]\) 吗？显然不是。
因为多加了一个 \(F(i-2)\)，所以其实对于这里面的数我们可以随便选，所以是 \(f[i-1][j][k] \times 2^{len_{i-2}}\)（这里设 \(len_i\) 代表 \(F(i)\) 的长度）吗？
因为只有当 \(k=n\) 的时候我们对于 \(F(i-2)\) 才没有什么限制，否则是有限制，所以综合就是这个式子：
而对于全部在 \(F(i-2)\) 中也是同理，就不多分析了，直接给出结论：
\[f[i][j][k] = \begin{cases} f[i-2][j][k] \times 2^{len_{i-1}} &j = 1\\ f[i-1][j][k] &j \not= 1 \end{cases} \]然后就是考虑跨区间的情况，其实也是很简单的：
\[f[i][j][k] = \sum_{p = j}^{k-1} f[i-1][j][p] \times f[i-2][p+1][k]。 \]初值也非常简单啦，\(f[0][i][i] = [s[i] = 0],f[1][i][i] = [s[i] = 1]\)
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 205;
int f[N][N][N],len[N],pw[N];
char s[N];
int mod(int x){
return x % MOD;
}
void add(int &x,int y){
y = mod(y);
x = mod(x + y);
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
signed main(){
int n,x;
scanf("%lld%lld",&n,&x);
scanf("%s",s+1);
len[0] = len[1] = 1;
pw[0] = 2,pw[1] = 2; //pw 直接记录对应的答案
for(int i=2; i<=x; i++){
len[i] = (len[i-1] + len[i-2]) % (MOD - 1); //卧槽？？欧拉定理
pw[i] = power(2,len[i]);
}
for(int i=1; i<=n; i++){
f[0][i][i] = (s[i] == '0');
f[1][i][i] = (s[i] == '1');
}
for(int i=2; i<=x; i++){
for(int j=1; j<=n; j++){
for(int k=j; k<=n; k++){
add(f[i][j][k],f[i-1][j][k] * (k == n ? pw[i-2] : 1));
add(f[i][j][k],f[i-2][j][k] * (j == 1 ? pw[i-1] : 1));
for(int p = j; p < k; p++){
add(f[i][j][k],f[i-1][j][p] * f[i-2][p+1][k]);
}
}
}
}
printf("%lld\n",f[x][1][n]);
return 0;
}
10.6
CF295D Greg and Caves
题目分析：
我们可以发现这个洞从上大小大小就是呈现：小-大-小 的趋势，所以我们知道能知道对于其中一半的方案是什么，就可以通过乘法原理得到整体的方案数。
我们也可以发现对于中间的这个长的洞在哪里是无所谓的，只要我们确定了它的长度以及这一整个洞有多少行我们就可以确定方案数。
所以其实可以考虑直接设 \(f[i][j]\) 表示整个洞有 \(i\) 行第 \(i\) 行的长度为 \(j\)，这从 \(1\) 到 \(i\) 洞的长度满足非严格单调递增。
所以转移就是显然地：
为啥 \(k\) 从 \(2\) 开始？因为我们至少是有两个黑块啊。
所以会发现这个很有道理，但是不对啊。那么原因是什么？
我们考虑对于一个长度为 \(k\) 的区间难道 \(i-1\) 只有一种选择吗？显然不是，他有 \(j - k + 1\) 种选择啊，所以最终的方程就是：
但是这样却会超时，很让人头大。冷静的分析一下会发现，我们假设从小到大枚举 \(j\) 那么我们每一次都是加一个前缀和，也就是 \(j \to j + 1\) 我们变化的就是 \(\sum_{k=2}^{j+1} dp[i-1][k]\)，所以维护一下前缀和就好了。
那么就考虑最终的答案是什么：
最后乘以一个 \(m - k + 1\) 也是同理的，因为显然不止一种方案
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 2e3+5;
int n,m,f[N][N],res,g[N][N];
int mod(int x){
return x % MOD;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=2;i<=m;i++) f[1][i]=1;
for(int i=2;i<=n;i++){
int sum = 0;
for(int j=2;j<=m;j++){
sum = mod(sum + f[i-1][j]);
f[i][j] = mod(f[i][j-1] + sum);
}
}
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
g[i][j] = mod(g[i-1][j] + f[i][j]);
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
res = mod(res + mod(mod(f[i][j] * g[n+1-i][j]) * (m - j + 1)));
printf("%lld\n",res);
return 0;
}
CF1620G Subsequences Galore
题目分析：
题意很抽象，稍微转化一下：\(f([t_1,t_2,\cdots,t_m])\) 代表的是 \(t_1,t_2,\cdots,t_m\) 的子序列的并集。
稍微尝试一下就会发现并集其实不好求，但是交集很好求。
因为我们的字母都是按顺序排列的，所以对于每种字母出现的次数取个 \(\min\) 然后乘起来就是交集，既然交集好球并集不好求显然可以直接容斥一下就好了。
那么最后的答案就是奇数个数的减去偶数个数的。
稍微形象一点就是这样的：
设 \(f(S)\) 表示 \(S\) 内这些字符串的子序列的交集，则：
其中 \(mn_c\) 代表 \(c\) 这种字符最少的出现次数。
设 \(g(S)\) 表示 \(S\) 内这些字符串的子序列的并集，可得：
可以对于奇数个和偶数个的分开处理，然后做一次高维前缀和就结束了。
但是在实现的时候需要注意，在计算 \(f(S)\) 的时候稍微精细一下，因为如果完全暴力计算的话是会被最大的一个点卡掉的。
代码：
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int MOD = 998244353;
const int N = 2e4+5;
int cnt[30][30],mn[1<<23],s[2][1<<24];
char t[N];
int mod(int x){
return x >= MOD ? x - MOD : x;
}
int lowbit(int x){
return x & (-x);
}
int get(int x){
int cnt = 0;
while(x){
cnt++;
x /= 2;
}
return cnt;
}
signed main(){
int n;
scanf("%lld",&n);
for(int i=1; i<=n; i++){
scanf("%s",t+1);
int m = strlen(t+1);
for(int j=1; j<=m; j++) cnt[i][t[j] - 'a']++;
}
for(int i=0; i<26; i++){
memset(mn,0x3f,sizeof(mn));
for(int j=1; j<(1<<n); j++){
int tmp1 = __builtin_popcount(j);
mn[j] = min(mn[j ^ lowbit(j)],cnt[get(lowbit(j))][i]);
s[tmp1&1][j] = ((s[tmp1&1][j]==0) ? (mn[j]+1) : (s[tmp1&1][j] * (mn[j] + 1))%MOD);
}
}
for(int i=1; i<=n; i++){ //高维前缀和
for(int j=1; j<(1<<n); j++){
if((j >> (i-1)) & 1){
s[1][j] = mod(s[1][j] + s[1][j ^ (1<<(i-1))]);
s[0][j] = mod(s[0][j] + s[0][j ^ (1<<(i-1))]);
}
}
}
int ans = 0;
for(int i=1; i<(1<<n); i++){
int tmp1 = 0,tmp2 = 0;
for(int j=1; j<=n; j++){
if((i >> (j-1)) & 1){
tmp1++;
tmp2+=j;
}
}
ans ^= tmp1 * tmp2 * mod(s[1][i] - s[0][i] + MOD);
}
printf("%lld\n",ans);
return 0;
}
11.7
CF886E Maximum Element
题目分析：
考虑如果 \(n\) 在位置 \(i\)，那么要使得返回值为 \(n\) 也就是前 \(i-1\) 个不会返回。
那么假设我们可以得到这么一个值：\(f[i]\) 代表 \([1,i]\) 的排列中间没有返回值的方案数。
那么我们最后的答案就是：
其实就是枚举一下 \(n\) 的位置，前面 \(i-1\) 个只需要关注其相对大小关系所以可以看作排列，后 \(n-i\) 个随便排都可以，因为显然都一定小于 \(n\)。
那么 \(f\) 数组怎么求呢，其实也是差不多的道理：
注意这个下界是 \(i-k+1\) 因为我们如果 \(i\) 的位置小于 \(i-k+1\) 那么因为后面的数一定会小于 \(i\)，所以至少 \(i\) 不会不返回。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
int f[N],fac[N],inv[N];
int mod(int x){
return ((x % MOD) + MOD)%MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
int C(int n,int m){
if(n < m) return 0;
return mod(mod(fac[n] * inv[m]) * inv[n - m]);
}
signed main(){
int n,k;
scanf("%lld%lld",&n,&k);
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = mod(fac[i-1] * i);
inv[n] = power(fac[n],MOD-2);
for(int i=n-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i + 1));
f[0] = 1;
int sum = 1;
for(int i=1; i<=n; i++){
f[i] = mod(fac[i-1] * sum);
sum = mod(sum + f[i] * inv[i]);
if(i - k >= 0) sum = mod(sum - f[i-k] * inv[i-k]);
}
int ans = fac[n];
for(int i=1; i<=n; i++){
ans = mod(ans - mod(C(n-1,i-1) * f[i-1]) * fac[n-i]);
}
printf("%lld\n",ans);
return 0;
}
CF1194F Crossword Expert
题目分析：
我们假设做出题目数为 \(i\) 的概率为 \(p[i]\) 的话，那么我们的答案就是：
\[\sum_{i=1}^n i\times p[i] \]对于这个式子有一个经典的转化，就是设 \(P[i]\) 表示做出题目数大于等于 \(i\) 的概率，那么答案就是：
\[\sum_{i=1}^n P[i] \]那么题目数量大于等于 \(i\) 其实就是前 \(i\) 道题目使用的时间小于等于 \(T\) 就好了。
那么我们设 \(S_i\) 表示在全部不加的情况下前 \(i\) 个数所使用的时间，那么 \(P[i]\) 就是：
也显然 \(T-S_i\) 大于 \(i\) 时没有意义，就直接取一个 \(\min\) 就好了。
但是这样我们依然需要 \(O(n^2)\) 去维护这个东西，不能接受。
但是我们可以发现一个事实就是：\(i\) 是均匀变化的，且 \(T-S_i\) 不升。
为了方便，我们设 \(S(n,m) = \sum_{i=0}^m \binom{n}{m}\)，稍微推一下就可以发现这个式子：
直接从小到大枚举 \(i\) 然后线性地推过去就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 5e6+5;
int fac[N],inv[N],f[N],sum[N];
int mod(int x){
return ((x % MOD)+MOD)%MOD;
}
int C(int n,int m){
if(n < m) return 0;
return mod(fac[n] * mod(inv[m] * inv[n - m]));
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
signed main(){
int n,t;
scanf("%lld%lld",&n,&t);
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = mod(fac[i-1] * i);
inv[n] = power(fac[n],MOD-2);
for(int i=n-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i + 1));
for(int i=1; i<=n; i++){
int x;scanf("%lld",&x);
sum[i] = sum[i-1] + x;
}
f[0] = 1;
int now = 0,s = 1;
for(int i=1; i<=n; i++){
if(t - sum[i] < 0) break;
int limit = min(i,t-sum[i]);
s = mod(2 * s - C(i-1,now));
while(now < limit) s = mod(s + C(i,now+1)),now++;
while(now > limit) s = mod(s - C(i,now)),now--;
f[i] = mod(s * power(power(2,i),MOD-2));
}
int ans = 0;
for(int i=0; i<=n; i++) ans = mod(ans + (f[i] - f[i+1]) * i);
printf("%lld\n",ans);
return 0;
}
11.10
[AGC002F] Leftmost Ball
题目分析：
最后我们形成的序列其实就是有 \(n\) 个白球，其他颜色的球各有 \(n-1\) 个，且满足任意一个前缀的白球数均大于等于其他颜色的种类数。
我们可以考虑设 \(f[i][j]\) 表示放了 \(i\) 个白球和 \(j\) 种其他颜色的球的方案数，转移就是去考虑从左到右第一个空位选择什么。
如果选择白球就是：
因为 \(j \le i-1\) 所以一定满足 \(j \le i\) 所以就是一定合法的。
如果选择其他颜色的球就是：
容易验证这样转移也一定是合法的。
解释一下这个方程：\(n - (j - 1)\) 就是剩下的没有选择的颜色里随便选一个，\(n \times k - i - (j-1) \times (k-1) - 1\) 就是我们剩下的没有放球的位置，最后减 \(1\) 是我们当前放的这一个球，\(k-2\) 就是剩下 \(k-2\) 球需要放啦。
所以总的式子就是：
需要特判一下 \(k=1\) 的情况。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2005;
const int MOD = 1e9+7;
int fac[N * N],inv[N * N],f[N][N];
int mod(int x){
return x % MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
int C(int n,int m){
if(n < m) return 0;
return mod(fac[n] * mod(inv[m] * inv[n-m]));
}
signed main(){
int n,k;
scanf("%lld%lld",&n,&k);
if(k == 1){
printf("1\n");
return 0;
}
fac[0] = 1;
for(int i=1; i<=n*k; i++) fac[i] = mod(fac[i-1] * i);
inv[n*k] = power(fac[n*k],MOD-2);
for(int i=n*k-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i + 1));
f[0][0] = 1;
for(int i=1; i<=n; i++){
f[i][0] = 1;
for(int j=1; j<=i; j++){
f[i][j] = mod(f[i-1][j] + mod(mod(f[i][j-1] * (n - (j - 1))) * C(n * k - i - (j-1) * (k-1) - 1,k-2)));
}
}
printf("%lld\n",f[n][n]);
return 0;
}
11.12
[八省联考 2018] 林克卡特树
题目分析：
首先可以发现切掉 \(k\) 条边相当于让原图变成了 \(k+1\) 个连通块，然后再串起来求一个树的直径其实就是让我们在树上求 \(k+1\) 条不相交的链，使得他们的权值和最大。
显然可以考虑树形 \(dp\)，就是设 \(dp[i][j][0/1/2]\) 代表以 \(i\) 为根的子树中有 \(j\) 条完整的链，其中 \(i\) 点的度数为 \(0/1/2\) 的最大值。
度数为 \(0\) 意味着没有相连的点，度数为 \(1\) 意味着它是链的一个端点，度数为 \(2\) 意味着有一条连接两个子树的链穿过它。
但是会发现这样状态就是 \(O(nk)\) 显然过不去，但是题目有一个提示就是我们要选择恰好 \(k\) 条边，那么就是可以考虑 \(wqs\) 二分了。
感性理解一下也可以发现，当我们以 \(k\) 为 \(x\) 轴以最优解为 \(y\) 轴，形成的图像就是一个凸的。
我们就每多选一条链多 \(mid\) 的惩罚值，二分直到最优解是 \(k\) 条链，然后跑一边将我们多加的这 \(l \times mid\) 减去就好了。
\(dp\) 的转移看代码就很好理解了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int INF = 1e10+5;
const double eps = 1e-5;
struct edge{
int nxt,to;
double val;
edge(){}
edge(int _nxt,int _to,double _val){
nxt = _nxt,to = _to,val = _val;
}
}e[2 * N];
struct node{
int y;
double x;
node(){}
node(double _x,int _y){
x = _x,y = _y;
}
}dp[N][4];
bool operator < (node a,node b){
if(a.x == b.x) return a.y > b.y;
return a.x < b.x;
}
node operator + (node a,node b){return {a.x + b.x,a.y + b.y};}
int cnt,head[2 * N];
double mid;
void add_edge(int from,int to,double val){
e[++cnt] = edge(head[from],to,val);
head[from] = cnt;
}
node mmx(node a,node b,node c){
return max(a,max(b,c));
}
void dfs(int now,int fath){
dp[now][0] = {0,0},dp[now][1] = {-INF,0},dp[now][2] = {mid,1}; //可以理解为一个自环啊
for(int i = head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(to == fath) continue;
dfs(to,now);
dp[now][2] = mmx(dp[now][2]+dp[to][3],dp[now][1]+dp[to][0]+node(e[i].val,0),dp[now][1]+dp[to][1]+node(e[i].val-mid,-1));
dp[now][1] = mmx(dp[now][1]+dp[to][3],dp[now][0]+dp[to][0]+node(e[i].val+mid,1),dp[now][0]+dp[to][1]+node(e[i].val,0));
dp[now][0] = dp[now][0] + dp[to][3];
//一定要特别注意这个 0,1,2 的顺序，不能用 to 更新之后再去更新 to 啊
}
dp[now][3] = mmx(dp[now][0],dp[now][1],dp[now][2]);
}
int check(){
dfs(1,0);
return dp[1][3].y;
}
signed main(){
int n,k;
scanf("%lld%lld",&n,&k);++k;
for(int i=1; i<n; i++){
int from,to,val;
scanf("%lld%lld%lld",&from,&to,&val);
add_edge(from,to,val);add_edge(to,from,val);
}
double l = -INF,r = INF;
while(r - l > eps){
mid = (l + r)/2;
int tmp = check();
if(tmp == k){
l = r = mid;
break;
}
if(tmp < k) l = mid;
else r = mid;
}
mid = l;dfs(1,0);
double ans = dp[1][3].x - l * k;
printf("%.0f\n",ans);
return 0;
}
[APIO2014] 连珠线
题目分析：
可以发现我们蓝线只会有两种形态：儿子 - 自己 - 儿子 或者 儿子 - 自己 - 父亲。
而我们也可以发现对于第一种情况一定存在当某一个点当作根的时候它是儿子 - 自己 - 父亲。
所以就可以考虑先随机找一个点当根，然后换根在所有的结果中取最大值就好了。
那么 \(dp\) 就是可以设 \(dp[i][0]\) 代表以 \(i\) 为根的子树 \(i\) 不在蓝线的中点的最大值，\(dp[i][1]\) 代表以 \(i\) 为根的子树 \(i\) 在蓝线的中点的最大值。
考虑 \(dp[i][0]\) 的转移，其实还是比较简单的：
其中 \(val[j]\) 代表 \((i,j)\) 这条边的边权。
考虑对于 \(dp[i][1]\) 的转移，我们可以发现对于某一个点最多是一条蓝线的中点，所以可以考虑枚举是哪一个儿子对应的蓝线的中点，而其他的儿子按 \(dp[i][0]\) 的方式转移就好了，所以也就是：
那么考虑换根，如果是 \(i \to j\) 会有什么影响。
首先 \(i\) 的 \(j\) 这个儿子没了，然后 \(i\) 的父亲变成了它的儿子，\(j\) 的父亲变成了它的儿子。
所以其实可以考虑直接每一个点维护一下缺少某一个点时的这些值，然后只需要考虑父亲变成儿子造成的影响就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int INF = 1e18+5;
struct edge{
int nxt,to,val;
edge(){}
edge(int _nxt,int _to,int _val){
nxt = _nxt,to = _to,val = _val;
}
}e[2 * N];
int ans = -INF,cnt,head[N],len[N],fa[N],f[N][2];
vector<int> g[N][2],son[N],mx[N];
void add_edge(int from,int to,int val){
e[++cnt] = edge(head[from],to,val);
head[from] = cnt;
}
int cost(int x){
return f[x][0] + len[x] - max(f[x][0],f[x][1] + len[x]);
}
void dfs(int now,int fath){
f[now][0] = 0,f[now][1] = -INF;
int mx1=-INF,mx2=-INF;
for(int i = head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(to == fath) continue;
dfs(to,now);
fa[to] = now;len[to] = e[i].val;son[now].push_back(to);
f[now][0] += max(f[to][0],f[to][1] + e[i].val);
if(cost(to) > mx1) mx2 = mx1,mx1 = cost(to);
else if(cost(to) > mx2) mx2 = cost(to);
}
f[now][1] = f[now][0] + mx1;
for(int i = head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(to == fath) continue; //g 记录除去这个点之后的 dp 值，mx 记录除去这个点之后的 1 的转移
g[now][0].push_back(f[now][0] - max(f[to][0],f[to][1] + e[i].val));
if(cost(to) == mx1){
g[now][1].push_back(g[now][0].back() + mx2);
mx[now].push_back(mx2);
}
else{
g[now][1].push_back(g[now][0].back() + mx1);
mx[now].push_back(mx1);
}
}
}
void solve(int now){
for(int i=0; i < son[now].size(); i++){
int to = son[now][i];
int fath = fa[now];
f[now][0] = g[now][0][i],f[now][1] = g[now][1][i];
if(fa[now]){
f[now][0] += max(f[fath][0],f[fath][1] + len[now]);
f[now][1] = f[now][0] + max(mx[now][i],f[fath][0] + len[now] - max(f[fath][0],f[fath][1] + len[now]));
}
ans = max(ans,f[to][0] + max(f[now][0],f[now][1] + len[to]));
solve(to);
}
}
signed main(){
int n;
scanf("%lld",&n);
for(int i=1; i<n; i++){
int from,to,val;
scanf("%lld%lld%lld",&from,&to,&val);
add_edge(from,to,val);add_edge(to,from,val);
}
dfs(1,0);
solve(1);
printf("%lld\n",ans);
return 0;
}
[HNOI2012]集合选数
题目分析：
可以在题目里发现一点提示 “集合论与图论”，那么考虑是不是可以从 \(x\) 向 \(2\times x\) 和 \(3 \times x\) 建图，那么我们把这个图拉直一下，就是一个网格图，我们题目的条件就是这个网格图相邻的点不同时被选择。这个网格图大概可以理解为这个样子：
这样会发现其实不是形成一个网格图，是很多个网格图，然后就是考虑一个网格图怎么求，然后多个网格图就直接乘起来就好了。
我们可以发现形成的网格图的行数和列数都不大，一个是 \(\log_2 n\) 一个是 \(\log_3 n\)，所以可以考虑直接状压，然后不能用相邻的点同时被选择就是状压的入门题了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+1;
int n,a[30][30],p[30],pw[30],f[20][200005],vis[200005];
void add(int &x,int y){
x = (x + y) % MOD;
}
int dp(int x){
for(int i=1; i<=18; i++) p[i] = 0;
a[1][1] = x;
for(int i=2; i<=18; i++){ //构造矩阵
if(a[i-1][1] * 2 <= n) a[i][1] = a[i-1][1] * 2;
else a[i][1] = n+1;
}
for(int i=1; i<=18; i++){
for(int j=2; j<=11; j++){
if(a[i][j-1] * 3 <= n) a[i][j] = a[i][j-1] * 3;
else a[i][j] = n + 1;
}
}
for(int i=1; i<=18; i++){ //得到每一行的状态
for(int j=1; j<=11; j++){
if(a[i][j] <= n) p[i] += pw[j-1],vis[a[i][j]] = true;
}
}
for(int i=1; i<=18; i++){
for(int j=0; j<=p[i]; j++){
f[i][j] = 0;
}
}
f[0][0] = 1;
for(int i=0; i<=18; i++){
for(int j=0; j<=p[i]; j++){ //因为符合条件的是一个前缀，所以 p[i] 一定是 111...111，所以直接枚举
for(int k=0; k<=p[i+1]; k++){
if(!(j & k) && !(k & (k << 1))){
add(f[i+1][k],f[i][j]);
}
}
}
}
//不可能到达第 18 行，因为 2^18 > 1e5，所以就充当终止条件了。
return f[18][0];
}
signed main(){
scanf("%lld",&n);
pw[0] = 1;
for(int i=1; i<=30; i++) pw[i] = pw[i-1] * 2;
int ans = 1;
for(int i=1; i<=n; i++) if(!vis[i]) ans = (ans * dp(i))%MOD;
printf("%lld\n",ans);
}
11.15
CF28C Bath Queue
题目分析：
显然可以考虑 \(dp\)。
然后用期望推了好久都没有推出来，那么就可以考虑使用期望的定义推，也就是算方案数。
那么就可以考虑设 \(dp[i][j][k]\) 表示前 \(i\) 个洗衣房，去了 \(j\) 个人，最大值为 \(k\) 的方案数。
转移也是很显然：
具体为什么要乘组合数，因为我们稍微模拟一下再手模一下会发现人和人之间是由区别的。
初值就是 \(dp[0][0][0] = 1\)
那么我们的答案就十分显然了：
但是这个题仿佛会爆 \(long long\)，那么用一下 \(double\) 就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
double C[N][N],dp[N][N][N];
int a[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) scanf("%d",&a[i]);
C[0][0] = 1;
for(int i=1; i<=n; i++){
C[i][0] = 1;
for(int j=1; j<=i; j++) C[i][j] = C[i-1][j] + C[i-1][j-1];
}
dp[0][0][0] = 1;
for(int i=0; i<m; i++){
for(int j=0; j<=n; j++){
for(int k=0; k<=n; k++){
for(int p=0; p<=n; p++){
if(j + p <= n) dp[i+1][j+p][max((p + a[i+1] - 1) / a[i+1],k)] += dp[i][j][k] * C[n-j][p];
}
}
}
}
double tmp = 0;
for(int i=1; i<=n; i++) tmp += dp[m][n][i]; //总方案数
double ans = 0;
for(int i=1; i<=n; i++) ans = ans + 1.0 * dp[m][n][i] * i / tmp;
printf("%.12f\n",ans);
return 0;
}
CF101D Castle
题目分析：
其实期望是没有什么意思的，因为我们只要可以求出最优的总的时间，除以 \(n-1\) 就是期望。
我们可以考虑设 \(dp[i]\) 表示以 \(i\) 为根的子树从 \(i\) 开始走题目要求的值是多少。
那么对于 \(dp[i]\) 它的值难道是 \(\sum_{j \in son[i]} dp[j]\) 吗？显然不是啊。
因为我们对于第 \(i\) 次访问的子树，一定会对 \(j > i\) 的子树 \(j\) 产生影响，所以只需要把影响算好就好了。
那么假设我们固定了一种转移顺序，也就是 \(v[i]\) 表示第 \(i\) 个访问的子树，那么我们的 \(dp\) 值就是：
这里设 \(sz[i]\) 代表 \(i\) 这棵子树的大小，\(w[i]\) 代表 \(fa[i]\) 到 \(i\) 权值的大小，\(s[i]\) 代表完全遍历 \(i\) 这棵子树并回到 \(i\) 花费的时间。
那么就是确定转移顺序了，这个转移顺序也就是一个很显然的套路。
我们考虑对于两个儿子 \(i,j\) 若 \(i\) 在前面更优意味着什么：
首先对于 \(i,j\) 谁在前谁在后对于在 \(i,j\) 后面的数是没有影响的，只是他们两个之间的影响。
稍微推一下就可以发现其实就是：
然后按照这个值排一下序按照排序后的序列直接做就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
struct edge{
int nxt,to,val;
edge(){}
edge(int _nxt,int _to,int _val){
nxt = _nxt,to = _to,val = _val;
}
}e[2 * N];
int cnt,head[N],dp[N],s[N],sz[N],val[N];
bool cmp(int a,int b){
return (s[a] + 2 * val[a]) * sz[b] < (s[b] + 2 * val[b]) * sz[a];
}
void add_edge(int from,int to,int val){
e[++cnt] = edge(head[from],to,val);
head[from] = cnt;
}
void dfs(int now,int fath){
sz[now] = 1;//记录子树大小
s[now] = 0; //记录遍历子树需要花费的时间
vector<int> son;
for(int i = head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(to == fath) continue;
dfs(to,now);son.push_back(to);
val[to] = e[i].val;
sz[now] += sz[to];s[now] = s[now] + s[to] + 2 * val[to];
}
sort(son.begin(),son.end(),cmp);
int tmp = 0;
for(int i : son) tmp += sz[i];
for(int to : son){
tmp -= sz[to];
dp[now] = dp[now] + dp[to] + sz[to] * val[to] + (s[to] + 2 * val[to]) * tmp;
}
}
signed main(){
int n;
scanf("%lld",&n);
for(int i=1; i<n; i++){
int from,to,val;
scanf("%lld%lld%lld",&from,&to,&val);
add_edge(from,to,val);add_edge(to,from,val);
}
dfs(1,0);
printf("%.8f\n",1.0 * dp[1] / (n - 1));
return 0;
}