呃呃，补不动了
开题顺序：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:\)
只会 \(60pts\) 的方法，可是考场上只用纯纯暴力写了 \(20pts\)，剪枝的方法还是得多学习下。
至于这个题，就是把相关联的量放到一个连通块里进行考虑，每个连通块 \(dfs\) 下，大大降低时间复杂度。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e3;
int cnt,gett,n,m1,m2,tot,head[MAXN + 5],fo[MAXN + 5][MAXN + 5],mu[MAXN + 5][MAXN + 5],ans;
bool vis[MAXN + 5];
vector<int> vv,src[MAXN + 5];
struct EDGE{
int u,v,next;
}edge[MAXN + 5];
void add(int u,int v){
++tot;
edge[tot].u = u;
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs1(int u,int now){
src[now].push_back(u);
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(!vis[v]){
vis[v] = 1;
dfs1(v,now);
}
}
}
void dfs(int cntt,int now){
if(cntt == src[now].size()){
for(int i = 0; i < vv.size(); i++){
int v = vv[i];
for(int j = 1; j <= mu[v][0]; j++){
if(!vis[mu[v][j]])return;
}
for(int j = 1; j <= fo[v][0]; j++){
if(vis[fo[v][j]])return;
}
}
++gett;
return;
}
vis[src[now][cntt]] = 1;
vv.push_back(src[now][cntt]);
dfs(cntt + 1,now);
vv.pop_back();
vis[src[now][cntt]] = 0;
dfs(cntt + 1,now);
}
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);
mu[u][++mu[u][0]] = v;
add(u,v);
add(v,u);
}
for(int i = 1; i <= m2; i++){
int u,v;
scanf("%lld%lld",&u,&v);
fo[u][++fo[u][0]] = v;
fo[v][++fo[v][0]] = u;
add(u,v);
add(v,u);
}
for(int i = 1; i <= n; i++){
if(!vis[i]){
vis[i] = 1;
dfs1(i,++cnt);
}
}
int ans = 1;
memset(vis,0,sizeof vis);
for(int i = 1; i <= cnt; i++){
gett = 0;
dfs(0,i);
ans *= gett;
}
cout << ans;
}
//5 3 3
//1 2
//1 4
//2 5
//3 5
//4 5
//3 5
题解：
\(T4:[WC]远古计算机\)
还不太会……再做做。。。