UOJ#209. 【UER #6】票数统计 组合+容斥

自己独立想出来的，开心.         

首先，对于 $x$ 不等于 $y$ 的情况，显然只限制前缀/后缀.    

然后如果没有 x 与 y 相等的情况的话我们完全可以枚举总的 1 的个数，然后限制后缀的就可以转化成限制前缀的.   

如果引入 x 与 y 相等的情况，也就是说要求前缀或后缀都填满也按照上述方式处理即可.  

但是要简单容斥一下，即 ans(前缀)+ans(后缀)-ans(前后缀)    

code:  

#include <bits/stdc++.h>    
#define N 5009   
#define ll long long
#define mod 998244353 
#define setIO(s) freopen(s".in","r",stdin) // , freopen(s".out","w",stdout)  
using namespace std;     
int C[N][N],n,m,lim,tot; 
struct node { int x,y; } ch[N];  
struct data 
{ 
    int x,y; 
    bool operator<(const data b) const { return x<b.x; }   
}tmp[N],A[N];         
void init() 
{
    C[0][0]=1;   
    for(int i=1;i<N;++i)
    {
        C[i][0]=1;  
        for(int j=1;j<=i;++j) C[i][j]=(ll)(C[i-1][j]+C[i-1][j-1])%mod;   
    }                                 
}         
int sol() 
{        
    sort(tmp+1,tmp+1+tot);     
    if(tmp[1].x==0&&tmp[1].y) return 0;     
    int ans=1,dist,det; 
    tmp[0].x=0,tmp[0].y=0;       
    for(int i=1;i<=tot;++i) 
    {    
        det=tmp[i].y-tmp[i-1].y;  
        dist=tmp[i].x-tmp[i-1].x;       
        if(dist<det||tmp[i].y<0||det<0) return 0;        
        ans=(ll)ans*C[dist][det]%mod;   
    }           
    return ans;   
}
int calc(int TOT)       
{
    // 总共有 TOT 个 1    
    tot=0;              
    for(int i=1;i<=m;++i) 
    {
        if(ch[i].x!=ch[i].y)  
        {   
            ++tot; 
            if(ch[i].x>ch[i].y) {        
                A[tot].x=ch[i].x;  
                A[tot].y=ch[i].y;    
            }
            else {   
                A[tot].x=n-ch[i].y;  
                A[tot].y=TOT-ch[i].x;              
            }     
        }
    }         
    ++tot;  
    A[tot].x=n;  
    A[tot].y=TOT;              
    int ans=0;             
    if(!lim) {       
        for(int i=1;i<=tot;++i) tmp[i]=A[i];   
        return sol();  
    }   
    else {       
        ++tot;   
        //============================ 只有前 
        A[tot].x=lim;  
        A[tot].y=lim;   
        for(int i=1;i<=tot;++i) tmp[i]=A[i];        
        (ans+=sol())%=mod;        
        //============================ 只有后   
        A[tot].x=n-lim;          
        A[tot].y=TOT-lim;      
        for(int i=1;i<=tot;++i) tmp[i]=A[i];  
        (ans+=sol())%=mod;     
        //============================ 前后都有      
        ++tot;  
        A[tot].x=lim;  
        A[tot].y=lim;  
        for(int i=1;i<=tot;++i) tmp[i]=A[i];   
        (ans+=mod-sol())%=mod;                 
        return ans; 
    }
}
void solve() 
{
    scanf("%d%d",&n,&m);      
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&ch[i].x,&ch[i].y);   
        if(ch[i].x==ch[i].y) lim=max(lim,ch[i].x);        
    }                            
    // 序列中有 i 个 1                         
    int ans=0;    
    for(int i=0;i<=n;++i) 
    {        
        ans+=calc(i);              
        if(ans>=mod) ans-=mod;
    }    
    printf("%d
",ans);   
    lim=tot=0;   
}
int main() 
{
    // setIO("input");     
    int T;  
    init();  
    scanf("%d",&T);   
    while(T--) solve();                     
    return 0; 
}