时间安排

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$ 然后成起来就是答案，用线段树维护即可