【UOJ #209】【UER #6】票数统计

75 阅读 0 评论 50 点赞

我是靠谱客的博主粗犷哈密瓜，最近开发中收集的这篇文章主要介绍【UOJ #209】【UER #6】票数统计，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

妹滋滋是一个善于编程的女孩子。
但是某一天，她一不小心把 UOJ 后台的票数统计程序写错了。
本来嘛在这种根本没有什么用的功能上出了 bug 也没有什么大关系，但是又有某一天，UOJ 突然就开始搞全民公投了。
这可怎么办呢？如果这个消息让别人知道的话自己肯定会被查表，更不要说让所有用户重新来投一次票了。
作为一个要强的女孩子，妹滋滋决定自力更生。
通过一些奥妙重重的方式，妹滋滋知道了一些关于这次全民公投的信息。
这次全民公投一共有 n 位用户排队参加，编号为 1 到 n。每一位用户要么投了通过，要么投了不通过。
有 m 个二元组 (xi,yi)，每个二元组给出这样一个信息： “前 xi 位用户中，恰好 yi 位投了通过” 和 “后 yi 位用户中，恰好有 xi 位投了通过” 这两句话中，至少有一句是成立的。
作为分析的第一步，她想要知道有多少种投票情况是满足她所得到的信息的。当然，可能所有投票情况都不满足条件。
答案可能很大，只需要输出对 998244353（7×17×2^23+1，一个质数）取模后的值。
$nleq5000,mleq 1000$

Analysis

显然，如果 $xineq yi$ ，两句话中有且仅有一句话是成立的。
如果 $forall xi>yi$ ，那么可以按限制区间长度排个序，扫一遍组合数乘起来就好了。
问题是，左右会互相限制。
考虑枚举总共的投通过的人数，这样就可以把右边的限制转化成左边的限制。
举个例子，长度为 $7$ 总共投通过人数为 $5,x=2,y=3$ .
我们可以变成 $x'=7-y=4,y'=5-x=3$
也即，最右边三个中选出两个，在总共选出 $5$ 个的情况下等价于最左边四个中选出三个。
所以我们可以把右限制变成左限制。
若 $exists xi=yi$ ，则只有最大的 $xi=yi$ 才有用（留给读者思考）。
所以，答案就是 $xi=yi$ 在左边+在右边-同时在两边的合法方案数。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=5010,M=1010,mo=998244353;
struct node
{
    ll x,y;
    bool p;
}a[M],b[M];
int n,m,num;
ll ans,mx,C[N][N];
bool cmp(node a,node b){return a.x<b.x;}
ll calc(int n)
{
    ll t=1;
    fo(i,1,n)
        if(b[i].x<b[i-1].x || b[i].y<b[i-1].y) return 0;
        else t=t*C[b[i].x-b[i-1].x][b[i].y-b[i-1].y]%mo;
    return t;
}
void lyd(int p)
{
    memset(b,0,sizeof(b));
    num=0;
    if(p==1 || p==3) b[++num].x=mx,b[num].y=mx;
    if(p==2 || p==3) b[++num].x=n-mx,b[num].y=-mx,b[num].p=1;
    fo(i,1,m)
        if(a[i].x>a[i].y) b[++num]=a[i];
        else
        if(a[i].x<a[i].y) b[++num].x=n-a[i].y,b[num].y=-a[i].x,b[num].p=1;
    b[++num].x=n,b[num].p=1;
    sort(b+1,b+num+1,cmp);
    fo(i,0,n)
    {
        fo(j,1,num)
            if(b[j].p) b[j].y+=i;
        if(p<3) ans=(ans+calc(num))%mo;
        else ans=(ans-calc(num)+mo)%mo;
        fo(j,1,num)
            if(b[j].p) b[j].y-=i;
    }
}
int main()
{
    fo(i,0,N-10)
        fo(j,0,i)
            if(j==0 || i==j) C[i][j]=1;
            else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
    int T;
    for(scanf("%d",&T);T;T--)
    {
        ans=mx=0;
        scanf("%d %d",&n,&m);
        fo(i,1,m)
        {
            scanf("%lld %lld",&a[i].x,&a[i].y);
            if(a[i].x==a[i].y) mx=max(mx,a[i].x);
        }
        if(!mx) lyd(0);
        else
        lyd(1),//left
        lyd(2),//right
        lyd(3);//both l&r
        printf("%lldn",ans);
    }
    return 0;
}