E - Cyclic Medians
看到中位数，就是经典套路：将\(\geq\)中位数的都赋值为\(1\)，\(<\)的赋值为\(0\)
那么对于数\(A\)，就等于\(\sum_{i=1}^{\infty}[A\geq i]\)
所以我们考虑枚举中位数，然后若其\(\leq A\)，那么就对答案贡献\(1\)
对于当前枚举的中位数\(mid\)，若当前正在操作的数对为\((0,0)\)或\((1,1)\)，那么这次更新后答案就与\(a\)无关；若当前操作的是\((0,1)\)或\((1,0)\)，那么这次更新后答案就还是与\(a\)有关
无关：更新后答案是\(\geq mid\)还是\(<mid\)与\(A\)和\(mid\)的大小无关
有关：更新后答案是\(\geq mid\)还是\(<mid\)由\(A\)和\(mid\)的大小决定
然后还有一点，就是当\(mid=p\)时最后答案取\(0\)的方案数与\(mid=v-p\)时最后答案取\(1\)的方案数相同，所以算这个答案时需要\(/2\)
考虑求出与\(a\)有关的方案数，然后用总方案数减去与\(a\)有关的方案数就是与\(a\)无关的方案数
因为每次取\(x_{i\%n}\)和\(y_{i\%m}\)作为一对，所以设\(a=i\%n\)，\(b=i\%m\)，\(g=\gcd(n,m)\)，\(n=g\times p\)，\(m=g\times q\)，那么有：
\[i=a+k_1n,i=b+k_2m\\
a+k_1n=b+k_2m\\
a+k_1\times g\times p=b+k_2\times g\times q\\
a\equiv b\mod g
\]
所以对于所有的数对，就可以分为\(g\)组互不干涉的组
那么要想与\(a\)有关，就必须数对中其中一个为\(0\)，另一个为\(1\)，那么方案数就为：
\[((mid-1)^{\frac ng}\times(v-mid+1)^{\frac mg}+
(mid-1)^{\frac mg}\times(v-mid+1)^{\frac ng})^g
\]
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,inv2=499122177;
int n,m,g,v,a,all,ans;
int power(int x,int y){
int ans=1;
for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) ans=1ll*ans*x%MOD;
return ans;
}
int gcd(int a,int b){
if(b) while((a%=b)&&(b%=a));
return a+b;
}
void add(int &a,int b){
a+=b;
if(a>=MOD) a-=MOD;
}
int main(){
scanf("%d%d%d%d",&n,&m,&v,&a);
g=gcd(n,m),ans=all=power(v,n+m);// mid=1
for(int i=2;i<=v;++i){
int now=power(1ll*power(i-1,n/g)*power(v-i+1,m/g)%MOD+1ll*power(i-1,m/g)*power(v-i+1,n/g)%MOD,g);
if(i<=a) add(ans,now);
int t=((1ll*all-now)%MOD+MOD)%MOD*inv2%MOD;
add(ans,t);
}
printf("%d",ans);
return 0;
}