比赛链接：https://codeforces.com/contest/1332
A. Exercising Walk
只要考虑最终位置是否在范围内，和特判 (x_1=x_2) 或者 (y_1=y_2) 的情况即可
#include <bits/stdc++.h>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
typedef long long ll;
ll t,a,b,c,d,x,y,x1,y1,x2,y2;
signed main(){
cin>>t;
while(t--){
cin>>a>>b>>c>>d>>x>>y>>x1>>y1>>x2>>y2;
int ans=(x1<=x-a+b && x-a+b<=x2
&& y1<=y-c+d && y-c+d<=y2);
if(a!=0 && x1==x2)ans=0;
if(c!=0 && y1==y2)ans=0;
cout<<(ans?"Yes":"No")<<endl;
}
return 0;
}
BCD我不会（大雾）
E. Height All the Same
高度限制在 ([l,r]) 内，其实和 ([0,r-l]) 是一样的，这样对问题稍微简化了一下
接下来讨论第一个情况，如果 (nm) 是奇数，我们发现无论初始方块堆成什么样都满足要求，因此此时答案是 ((r-l+1)^{nm})
第二种情况复杂很多，如果 (nm) 是偶数，我们发现所有初始方块中大约有一半是满足要求的，因此答案大约是 (dfrac {(r-l+1)^{nm}}{2})，然后发现有时候除不尽，于是变形成 (lceildfrac {(r-l+1)^{nm}}{2} ceil) ，一交，ac（此处%zkx，太强了）
（ps：(lceil x ceil=) 大于等于 (x) 的最小整数）
接下来我来证明一下这个公式为什么是对的
令 (h={r-l+1})，因为放两个方块不改变方块总数的奇偶性，所以有以下结论：满足要求当且仅当 放了奇数个方块的位置个数 是偶数个（重要定理）
对一个位置，放奇数个方块有 (lfloor dfrac h 2 floor) 个方式，放偶数个方块有 (lceil dfrac h 2 ceil)
我们令 (a=lfloor dfrac h 2 floor)，(b=lceil dfrac h 2 ceil)，(x=) 放了奇数个方块的位置个数，那么放了偶数个方块的位置个数为 (nm-x)
因此所有方案数（不考虑总方块数是否为偶数）为 (h^{nm}=sumlimits_{x=0}^{nm}C_{nm}^x a^x b^{nm-x})（右式既可以二项式定理展开，也可以手推出来，怎么推的我不讲了）
根据重要定理，我们发现放了奇数个方块的位置个数（就是 (x)）是偶数的时候才对答案有贡献，因此
(ans=sumlimits_{x=0..nm 且 x 是偶数}C_{nm}^x a^x b^{nm-x})
又因为叉哥牛逼（此处%叉哥），我们发现如果对 ((a+b)^{nm}+(a-b)^{nm}) 两个幂二项式展开，所有 (nm-x) 是奇数的项都会消掉，只剩下两倍的 (nm-x) 是偶数的项之和，我们需要的正好是 (x) 是偶数的项之和，这不是一回事吗.jpg
所以答案化简为 (ans=dfrac {(a+b)^{nm}+(a-b)^{nm}}{2}=dfrac {h^{nm}+(a-b)^{nm}}{2})，如果 (a=b)，(ans=dfrac {h^{nm}}2)，如果 (a=b-1)，(ans=dfrac{h^{nm}+1}{2})，这个形式正好等价于 (lceildfrac {(r-l+1)^{nm}}{2} ceil)，证毕
#include <bits/stdc++.h>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
//mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
const ll mod=(0?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;} ll getinv(ll v,ll m=mod){return qpow(v,m-2,m);}
ll n,m,l,r;
signed main(){
cin>>n>>m>>l>>r;
ll h=r-l+1;
if(n*m%2==1){
cout<<qpow(h,n*m)<<endl;
}
else{
cout<<(qpow(h,n*m)+(h%2==1))*getinv(2)%mod<<endl;
}
return 0;
}
F. Independent Set
遇到树上计数问题，还是独立集相关的，果断考虑树型dp
首先我们不考虑删边的情况。独立集其实就要求染色的所有点两两不相邻，也就是说如果一个点染色了，它只能连接不染色的点（乘以儿子不染色的状态数），如果一个点不染色，它想怎么连接就怎么连接（乘以儿子染色的状态数加不染色的状态数）
也就是以 (u) 为根的子树中，令 (col[u]) 是 (u) 染色的状态数，(uncol[u]) 是 (u) 不染色的状态数，状态转移方程是
(col[u]=prodlimits_{v∈son(u)}uncol[v]\uncol[u]=prodlimits_{v∈son(u)}(col[v]+uncol[v]))
当然这是不删边的情况
如果考虑删边，我们要多加一个状态 (del[u]) 表示 (u) 被删掉了。三个状态，染色、不染色、删掉，清晰如我，注意删掉其实可以复活（下面会解释）
接下来分别讨论三个状态
如果点 (u) 被染色了，对于它的儿子 (v)，它可以选择不连 (v)（这时候 (v) 长什么样都可，(col[v]+uncol[v]+del[v])），也可以选择连 (v)（这时候 (v) 不能是染色状态，如果 (v) 是不染色状态，完全可以，(uncol[v])；如果 (v) 是删除状态，其实意思是让 (v) 复活，只要 (v) 不染色即可，(del[v])）
转移方程 (col[u]=prodlimits_{v∈son(u)}(col[v]+2uncol[v]+2del[v])-del[u])
（至于为什么 (Pi) 外要减去 (del[u]) 呢，因为 (u) 的边全部删掉后 (u) 就是删除状态了不是染色状态，所以要减一下）
如果点 (u) 不染色，对于它的儿子 (v)，它可以选择不连 (v)（这时候 (v) 长什么样都可(col[v]+uncol[v]+del[v])），也可以选择连 (v)（这时候 (v) 可以染色or不染色，(col[v]+uncol[v])，也可以让删除的 (v) 复活，这时候 (v) 也是可以染色or不染色，(2del[v])）
转移方程 (uncol[u]=prodlimits_{v∈son(u)}(2col[v]+2uncol[v]+3del[v])-del[u])
（这里减去的 (del[u]) 也是同样的）
如果点 (u) 删除，那么再怎么说都不连 (v) 了，所以直接 (col[v]+uncol[v]+del[v])
转移方程 (del[u]=prodlimits_{v∈son(u)}(col[v]+uncol[v]+del[v]))
最后答案是根节点的 (col+uncol+del-1)，减1是为了排除所有点都被删除的情况
#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define vector basic_string
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=300010; typedef long long ll; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;}
const int mod=(0?1000000007:998244353);
ll col[N],uncol[N],del[N],vis[N];
vector<int> a[N];
#define M(x) ((x)%mod)
void dfs(int x){
vis[x]=1;
col[x]=uncol[x]=del[x]=1;
for(auto p:a[x])
if(!vis[p]){
dfs(p);
col[x]=col[x]*M(col[p]+2*uncol[p]+2*del[p])%mod;
uncol[x]=uncol[x]*M(2*col[p]+2*uncol[p]+3*del[p])%mod;
del[x]=del[x]*M(col[p]+uncol[p]+del[p])%mod;
}
col[x]=(col[x]-del[x])%mod;
uncol[x]=(uncol[x]-del[x])%mod;
}
signed main(){
int n=read();
repeat(i,0,n-1){
int x=read()-1,y=read()-1;
a[x]+=y; a[y]+=x;
}
dfs(0);
cout<<((col[0]+uncol[0]+del[0]-1)%mod+mod)%mod<<endl;
return 0;
}