uoj#273. 【清华集训2016】你的生命已如风中残烛（组合数学）-白红宇

uoj#273. 【清华集训2016】你的生命已如风中残烛（组合数学）

阅读量：4931 次

发布时间：2019-06-11

本文共 1003 字，大约阅读时间需要 3 分钟。

~~一道打表题~~

我们把那些普通牌的位置看成\(-1\)，那么就是要求有多少个排列满足前缀和大于等于\(1\)

考虑在最后放一个\(-1\)，那么就是除了\(m+1\)的位置前缀和都要大于等于\(1\)

\(m+1\)个数的圆排列的方案数为\(m!\)，然后对于每一个圆排列，肯定存在一个前缀和最小且最右边的位置，那么它后面的所有位置肯定前缀和都大于等于\(1\)，而对于这个位置如果不把它放最后肯定会有前缀和小于\(1\)

所以对于每一种圆排列有且仅有一种摆放方式合法

然而此时最后的这个\(-1\)不一定是我们加进去的\(-1\)，可能是原来排列里的，于是要除以\(-1\)的个数\(m+1-n\)

综上答案为\(\frac{m!}{m+1-n}\)

//minamoto#include
    
     #include
     
      #include
      #define R register#define fp(i,a,b) for(R int i=a,I=b+1;i
       
        I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)const int P=998244353;inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);    return res;}int n,m,x,res=1;int main(){//  freopen("testdata.in","r",stdin);    scanf("%d",&n);    fp(i,1,n)scanf("%d",&x),m+=x;    fp(i,2,m)res=mul(res,i);    res=mul(res,ksm(m-n+1,P-2));    printf("%d\n",res);    return 0;}

转载于:https://www.cnblogs.com/bztMinamoto/p/10240247.html

你可能感兴趣的文章