• A. Exercising Walk
• BCD 我不会（大雾）
• E. Height All the Same
• F. Independent Set

比赛链接 (opens new window)

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}$，然后发现有时候除不尽，于是变形成 $\lceil\dfrac {(r-l+1)^{nm}}{2}\rceil$ ，一交，ac（此处 %zkx，太强了）。

（ps：$\lceil x \rceil=$ 大于等于 $x$ 的最小整数）

接下来我来证明一下这个公式为什么是对的。

令 $h={r-l+1}$，因为放两个方块不改变方块总数的奇偶性，所以有以下结论：满足要求当且仅当 放了奇数个方块的位置个数 是偶数个（重要定理）。

对一个位置，放奇数个方块有 $\lfloor \dfrac h 2\rfloor$ 个方式，放偶数个方块有 $\lceil \dfrac h 2\rceil$。

我们令 $a=\lfloor \dfrac h 2\rfloor$，$b=\lceil \dfrac h 2\rceil$，$x=$ 放了奇数个方块的位置个数，那么放了偶数个方块的位置个数为 $nm-x$。

因此所有方案数（不考虑总方块数是否为偶数）为 $h^{nm}=\sum\limits_{x=0}^{nm}C_{nm}^x a^x b^{nm-x}$（右式既可以二项式定理展开，也可以手推出来，怎么推的我不讲了）。

根据重要定理，我们发现放了奇数个方块的位置个数（就是 $x$）是偶数的时候才对答案有贡献，因此：

ans=\sum\limits_{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}$，这个形式正好等价于 $\lceil\dfrac {(r-l+1)^{nm}}{2}\rceil$，证毕。

#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]=\prod\limits_{v∈son(u)}uncol[v]\\uncol[u]=\prod\limits_{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]=\prod\limits_{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]=\prod\limits_{v∈son(u)}(2col[v]+2uncol[v]+3del[v])-del[u]。

（这里减去的 $del[u]$ 也是同样的。）

---

如果点 $u$ 删除，那么再怎么说都不连 $v$ 了，所以直接 $col[v]+uncol[v]+del[v]$。

转移方程 del[u]=\prod\limits_{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;
}