[uoj#209][UER#6A]票数统计

54 阅读 0 评论 36 点赞

我是靠谱客的博主无语小兔子，最近开发中收集的这篇文章主要介绍[uoj#209][UER#6A]票数统计，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

给出n个数，每个数是0或1.
再给出m个限制，每个限制(x,y)表示“前x个数中有y个1”或“后y个数中有x个1”
求这样的序列的个数。
n<=5000,m<=1000

Solution

再一次被UER给虐了。
其实这道题劼鏼爷已经讲的很清楚了。（扑通扑通跪下来）
当x!=y的时候，很显然已经确定这个限制是限制前缀还是后缀的。
当x=y的时候，我们只需要保留最大的那个x就行了。（显然）
然后，我们可以用容斥。
答案是x=y是前缀限制的个数+后缀限制的个数-前后缀都限制的个数。
那么，现在就是有一堆前后缀的限制，让你求方案数。
如果只有前（后）缀，那么，就相当于把这n个数划分成了m个区间，对于每一个区间单独限制。一堆组合数乘起来就好了。
那么，前后缀都有的话，我们就可以把后缀转化成前缀。（反之亦然）
枚举1的总和就行了。
劼鏼大法好！（刷队形）

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 5005
using namespace std;
typedef long long ll;
const int mo=998244353;
struct note{int x,y,bz,ty;}a[N],p[N];
bool cmp(note x,note y) {return x.x<y.x;}
int c[N][N],n,m,ty,x,y,z,ans,tot;
int main() {
    c[0][0]=1;
    fo(i,1,N-5) {
        c[i][0]=1;
        fo(j,1,i) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;
    }
    for(scanf("%d",&ty);ty;ty--) {
        scanf("%d%d",&n,&m);tot=z=ans=0;
        fo(i,1,m) {
            scanf("%d%d",&x,&y);
            if (x>y) a[++tot].x=x,a[tot].y=y,a[tot].bz=0,a[tot].ty=0;
            else if (x<y) a[++tot].x=n-y,a[tot].y=x,a[tot].bz=1,a[tot].ty=0;
            else z=max(z,x);
        }
        a[++tot].x=z;a[tot].y=z;a[tot].bz=0;a[tot].ty=1;
        a[++tot].x=n-z;a[tot].y=z;a[tot].bz=1;a[tot].ty=2;
        sort(a+1,a+tot+1,cmp);
        fo(type,1,3) 
            fo(i,1,n) {
                int cnt=0;bool pd=0;
                fo(j,1,tot) {
                    if (a[j].ty==type) continue;
                    p[++cnt].x=a[j].x;
                    if (a[j].bz) p[cnt].y=i-a[j].y;
                    else p[cnt].y=a[j].y;
                    if (p[cnt].y<0||p[cnt].y>i) {pd=1;break;}
                    if (p[cnt].x<p[cnt].y) {pd=1;break;}
                    if (p[cnt].x-p[cnt-1].x<p[cnt].y-p[cnt-1].y) {pd=1;break;}
                    if (p[cnt].y-p[cnt-1].y<0) {pd=1;break;}
                }
                if (pd) continue;int sum=1;
                fo(j,1,cnt) sum=(ll)sum*c[p[j].x-p[j-1].x][p[j].y-p[j-1].y]%mo;
                sum=(ll)sum*c[n-p[cnt].x][i-p[cnt].y]%mo;
                if (type<=2) ans=(ans+sum)%mo;
                else ans=(ans-sum+mo)%mo;
            }
        printf("%dn",(ans%mo+mo)%mo);
    }
}