做UER的A题涨信心

首先我们注意到这个所谓的至少有一条正确在\(x\)和\(y\)不相等的时候非常弱，当\(x<y\)时，只有可能是后\(y\)位用户有\(x\)个通过；当\(x>y\)时，只有可能是前\(x\)位用户有\(y\)个通过。也就是说这些信息都能被转化成一些用来限制前后缀和的信息。

设\(pre_i\)表示序列的前缀和，对于一条前\(x\)位用户有\(y\)个通过的限制，我们可以拆成\(pre_x=y\)；对于一条后\(y\)位用户有\(x\)个通过的信息，可以视为\(pre_n-pre_{n-y}=x\)，即\(pre_{n-y}=pre_n-x\)。

如果我们知道\(pre_n\)的值，那么就只剩下了一些前缀和的信息了。所以我们可以直接枚举\(pre_n\)的值。这些关于前缀和的限制又将整个序列分割成了一些区间，每个区间的区间和也都被限制好了，直接使用组合数把每个区间的方案算出来就好了，答案就是每一个区间组合数的乘积。

但是上述的做法均不能处理\(x=y\)的情况，当\(x=y\)的时候，意味着有一个长度为\(x\)的前缀或后缀全都是\(1\)。这个\(x\)越大限制性必然越强，于是我们只需要考虑最大的\(x=y\)，满足了最大的\(x=y\)剩下的\(x=y\)必然也都满足了。

我们枚举这个\(x=y\)限制前缀还是限制后缀，限制前缀就拆成\(pre_x=x\)，限制后缀就拆成\(pre_{n-x}=x\)。但是如果有一种方案既有一段全是\(1\)的前缀，也有一段全是\(1\)的后缀，就会被计算两次。所以我们把两条限制条件都加上，再减掉这样的方案就好了。

代码

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=5e3+5;const int mod=998244353;int T,n,m,M;int fac[maxn],ifac[maxn],inv[maxn];int a[maxn],b[maxn],c[maxn],d[maxn],t[2],pre[maxn];inline int C(int n,int m) {    return m>n?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}inline int solve(int sum) {    for(re int i=1;i<=t[0];i++) {        if(pre[a[i]]!=-1&&pre[a[i]]!=c[i]) return 0;        pre[a[i]]=c[i];    }    for(re int i=1;i<=t[1];i++) {        if(pre[n-b[i]]!=-1&&pre[n-b[i]]!=sum-d[i]) return 0;        pre[n-b[i]]=sum-d[i];     }    if(pre[0]!=-1&&pre[0]!=0) return 0;    pre[0]=0;int l=0,tot=1;    for(re int i=1;i<=n;i++) {        if(pre[i]==-1) continue;        if(pre[i]
     
      y) a[++t[0]]=x,c[t[0]]=y;            if(x==y) M=max(M,x);        }        int ans=0,now=M;        for(re int i=1;i<=t[0];i++) now=max(now,c[i]);        for(re int i=1;i<=t[1];i++) now=max(now,d[i]);        for(re int i=now;i<=n;i++) {            memset(pre,-1,sizeof(pre));            pre[n]=i,pre[M]=M;            ans=(ans+solve(i))%mod;            if(!M) continue;            memset(pre,-1,sizeof(pre));            pre[n]=i,pre[n-M]=i-M;            ans=(ans+solve(i))%mod;            memset(pre,-1,sizeof(pre));            pre[n]=i,pre[M]=M;pre[n-M]=i-M;            if(M==n-M&&M!=i-M) continue;            ans=(ans-solve(i)+mod)%mod;        }        printf("%d\n",ans);    }    return 0;}