呃呃，补不动了
开题顺序：T3->T1->T2
\(T1:\)

考场上想了个 \(n^2\) 的 \(DP\)，只有六十……想了快一个小时。得知正解就是卡特兰数时追悔莫及。(参见卡特兰数)样例输入为 \(5\) \(3\)，根据样例，把每种情况的 \(x_i\) 的指数写出来。

对于每个 \((a,b,c,d,e)\)，\(a\) 表示的就是该方案下 \(x_1\) 的指数，以此类推。
再求一个前缀和：

不妨求前缀和后每个五元组看作五个坐标，纵坐标为 \(i\)，横坐标就为求得的五元组中的 \(a_i\)。显然，这五个点连起来后的路径的终点是 \((5,3)\)。要求路径上的所有点都不在 \(y = x + 3\) 上。显然，最终的答案就是从 \((0,0)\) 到 \((n - k + 1,n)\) 的路径总数。考虑用卡特兰数来解决。
答案即为 \(2n - k + 1 \choose n - k + 1\) - \(2n - k + 1 \choose n - k\)。

所以实在不会做的时候还是得想想这些数学方面的知识？

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5;
const int MOD = 998244353;
int ifac[MAXN + 5],n,k,fac[MAXN + 5];
int qpow(int a,int n){
	int ret = 1;
	while(n){
		if(n & 1)ret = ret * a % MOD;
		a = a * a % MOD;
		n /= 2;
	}
	return ret;
}
int c(int n,int m){
	return fac[n] * ifac[n - m] % MOD * ifac[m] % MOD;
}
signed main(){
	freopen("expand.in","r",stdin);
	freopen("expand.out","w",stdout);
	scanf("%d%d",&n,&k);
	fac[0] = 1;
	for(int i = 1; i <= 2 * n; i++){
		fac[i] = fac[i - 1] * i % MOD;
	}
	ifac[2 * n] = qpow(fac[2 * n],MOD - 2);
	for(int i = 2 * n; i >= 1; i--){
		ifac[i - 1] = ifac[i] * i % MOD;
	}
	int ans = ((c(n + n - k + 1,n - k + 1) - c(n + n - k + 1,n - k)) % MOD + MOD) % MOD;
	cout << ans;
}

\(T2:\)

还是不会，只会用 \(bitset\) 模拟下，\(bitset\) 的加法操作的函数还是要背背。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5;
bitset<MAXN> tmp,one;
bitset<MAXN> add(bitset<MAXN> a,bitset<MAXN> b){
	return (b.any() ? add((a ^ b),((a & b) << 1)) : a);
}
signed main(){
	freopen("conj.in","r",stdin);
	freopen("conj.out","w",stdout);	
	cin >> tmp;
	one[0] = 1;
	int ans = 0;
	while(tmp.count() != 1 || tmp[0] != 1){
		ans++;
		if(tmp[0] == 1){
			tmp = add(tmp,tmp << 1);
			tmp = add(tmp,one);
		}
		else tmp >>= 1;
	}
	cout << ans;
}

放个题解先——

\(T3:\)

考场上只用纯纯暴力写了 \(20pts\)，剪枝的方法还是得多学习下。

正解还没弄懂，但是会能水过这题数据的方法。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5;
int n,m1,m2,ans,vis[MAXN + 5][2];//vis[i][0]为1表示一定不能选，vis[i][1]为1表示一定要选 
struct EDGE{
	int u,v,w;
};
vector<EDGE> g[MAXN + 5];
void add(int u,int v,int w){
	EDGE a = (EDGE){u,v,w};
	g[u].push_back(a);
}
void dfs(int cnt,int sum){
	if(cnt == n + 1){
		ans += sum;
		return; 
	}
	if(!vis[cnt][0] && !vis[cnt][1]){//假如没有任何限制 
		if(!g[cnt].size()){
			dfs(cnt + 1,sum * 2);//若没有任何宝藏跟它有关系，就可选可不选，方案数因此乘二 
			return;
		}
		vis[cnt][0]++;
		dfs(cnt + 1,sum);//不选这个东西 
		vis[cnt][0]--;
		bool flag = 0;
		for(int i = 0; i < g[cnt].size(); i++){
			int v = g[cnt][i].v;
			int id = g[cnt][i].w;
			if(vis[v][id ^ 1]){//发现矛盾 
				flag = 1;
				break;
			}
			if(v < cnt && !vis[v][0] && !vis[v][1]){//如果跟它有关系的物品之前可选可不选，那么到它这儿了就只能有一种选法 
				sum /= 2;
			}
			vis[v][id]++;//标记一定要选 
		}
		if(!flag)vis[cnt][1]++,dfs(cnt + 1,sum),vis[cnt][1]--;//合法，就继续递归 
		for(int i = 0; i < g[cnt].size(); i++){
			int v = g[cnt][i].v;
			int id = g[cnt][i].w;
			if(vis[v][id ^ 1]){
				break;
			}
			vis[v][id]--;
		}
	}
	else if(vis[cnt][0])dfs(cnt + 1,sum);
	else{
		bool flag = 0;
		for(int i = 0; i < g[cnt].size(); i++){
			int v = g[cnt][i].v;
			int id = g[cnt][i].w;
			if(vis[v][id ^ 1]){
				flag = 1;
				break;
			}
			if(v < cnt && !vis[v][0] && !vis[v][1]){
				sum /= 2;
			}
			vis[v][id]++;
		}
		if(!flag)dfs(cnt + 1,sum);
		for(int i = 0; i < g[cnt].size(); i++){
			int v = g[cnt][i].v;
			int id = g[cnt][i].w;
			if(vis[v][id ^ 1]){
				break;
			}
			vis[v][id]--;
		}
	}
}
signed main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout); 
	scanf("%lld%lld%lld",&n,&m1,&m2);
	for(int i = 1; i <= m1; i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v,1);//两个宝藏之间有关系，就连一条边 
	}
	for(int i = 1; i <= m2; i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v,0);
	}
	dfs(1,1);
	cout << ans;
}

思路在注释里标出来了。感觉能从这个方法里学的还是搜索状态的表示？不像我一开始那样状态在转移是捋不清楚，导致有思路，但是写不出来……
题解：

\(T4:[WC]远古计算机\)
还不太会……再做做。。。