时间安排
8:00~8:40
看题，除a没有会的
8:40~9:20
写完a
9:20~12:00
一直看b，想差分约束，然后坐牢
总结
- 智力感觉有所下降
- 认真看题面
题解
A
n遍dijkstra，然后建图，再跑dijkstra
B
#include <bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
ll C[3005][3005],fact[3005];
void init()
{
C[0][0]=1;
for (int i=1;i<=3003;i++)
for (int j=0;j<=i;j++)
{
if (i==1 || j==0) C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
fact[0]=1;
for (int i=1;i<=3003;i++) fact[i]=fact[i-1]*i%mod;
return;
}
void add(ll &x,ll y) {x+=y; x%=mod; return;}
ll dp[3005][3005];
int suml[3005],sumr[3005];
int m,n,l,r;
int main()
{
init();
cin>>m>>n;
for (int i=1;i<=m;i++) {cin>>l>>r; suml[l]++; sumr[r]++;}
for (int i=1;i<=n;i++) suml[i]=suml[i-1]+suml[i],sumr[i]=sumr[i-1]+sumr[i]; // 左区间 <=i 的人数（不一定覆盖到i）， 右区间 <=i 的人数
dp[0][0]=1;
for (int i=0;i<n;i++) // n 个 拍卖品
for (int j=0;j<=m;j++) // m 个人
if (dp[i][j]) //前i列，有j个R未满足
{
l=suml[i+1]-suml[i]; //第 i+1 列有多少个左区间的端点，一定需要在这里被满足的左区间
r=sumr[i]-j; //之前满足了这么多个右区间
int rr=sumr[i+1]-sumr[i]; //这第i+1列一共有这么多个右区间的左端点
int lef=i+1-r-suml[i]; //现在前面还剩下lef个列可以选
if (lef<0) continue; //如果lef<0没可能
//case1：这列选给了一个R
if (j+rr>=1 && lef>=1) add(dp[i+1][j+rr-1],dp[i][j]*(j+rr)%mod*C[lef-1][l]%mod*fact[l]%mod);
//case2：这列没选给一个R
if (lef>=l) add(dp[i+1][j+rr],dp[i][j]*C[lef][l]%mod*fact[l]%mod);
}
cout<<dp[n][0]<<endl;
}
C
打表发现 \(0\sim2^k-1\) 中二进制表示下有奇数个 \(1\) 的数（下面统称为 \(odd_k\)）和有偶数个 \(1\) 的数（下面统称为 \(eve_k\)）个数相同，严格证明考虑数学归纳法：
\[特殊的,当k=0时,odd_0\not=eve_0 当k=1时,显然有odd_1=eve_1 \\ 当k=2时,odd_2=odd_1+eve_1,eve_2=eve_1+odd_1，考虑2^1\sim2^2-1相当于在0\sim2^1-1中每个数前加一个1 \\ 当k=3时,odd_3=odd_2+eve_2,eve_3=eve_2+odd_2 \\ \cdots 当k=n时,odd_n=odd_{n-1}+eve_{n-1},eve_n=eve_{n-1}+odd_{n-1} \]证毕
更进一步的
可以得到任意 \(2^{c_1}+2^{c_2}+...+2^{c_n}\ (c_i\not=0)\) 的 \(eve\) 和 \(odd\) 相等，所以只需要特判是否含有 \(2^0\)
剩下的只需要用做区间恢复，然后统计 \(odd\) 和 \(eve\) 然后成起来就是答案，用线段树维护即可
D
首先，每个人都是独立的，也就是说，可以分开求每个人的期望
每个点被选的概率相等，当选了 \(x\) 个点时，概率就等于 \(\binom{n}{x}\)，再考虑求一个点对被选中的概率
对于一个固定的点对 \((a,b)\)，其出现次数就相当于同时选了这个点对对应的 \(a\) 和 \(b\)，剩下的点随便选，也就是 \(\binom{n-2}{x-2}\)
那么对于这个点对，被选中的概率就是 $$\frac{\binom{n-2}{x-2}}{\binom{n}{x}}$$
最后答案就是 总的满足条件的点对数量\(\times\)固定点对被选中的概率 得到的就是选中点对的期望
现在已经求出 固定点对被选中的概率，对于 总的满足条件的点对数量 可以直接点分治 \(O(nlogn)\)求得
标签：lef,9.24,eve,模拟,binom,odd,dp,mod From： https://www.cnblogs.com/atom-/p/17726584.html