当前位置: 首页 > news >正文

CF960G Bandit Blues(第一类斯特林数)

传送门

可以去看看litble巨巨关于第一类斯特林数的总结

\(f(i,j)\)\(i\)个数的排列中有\(j\)个数是前缀最大数的方案数,枚举最小的数的位置,则有递推式\(f(i,j)=f(i-1,j-1)+(i-1)\times f(i-1,j)\)

这个就是第一类斯特林数

第一类斯特林数中\(S_1(n,m)\)\(\prod_{i=0}^{n-1}(x+i)\)\(x^m\)的系数,可以用分治\(FFT\)做到\(O(n\log^2n)\)的复杂度

首先\(n\)肯定是前缀最大值,所以题目要求的\(a-1\)个数一定都在\(n\)前面,\(b-1\)个数一定都在\(n\)后面。设整个序列中没有\(n\),前缀最大值的位置分别为\(p_1,p_2,...,p_k\),可以把每个\([p_i,p_{i+1}-1]\)看成一块,那么可以产生\(a+b-2\)块,然后选择其中的\(b-1\)块整个翻转然后放到\(n\)的后面,所以答案就是\[S_1(n-1,a+b-2)\times C_{a+b-2}^{b-1}\]

//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(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)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=5e5+5,P=998244353,Gi=332748118;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
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 A[19][N],O[N],r[N];
int n,m,a,b;
void NTT(int *A,int ty,int lim){
    fp(i,0,lim-1)if(i<r[i])swap(A[i],A[r[i]]);
    for(R int mid=1;mid<lim;mid<<=1){
        R int I=(mid<<1),Wn=ksm(ty==1?3:Gi,(P-1)/I);O[0]=1;
        fp(i,1,mid-1)O[i]=mul(O[i-1],Wn);
        for(R int j=0;j<lim;j+=I)for(R int k=0;k<mid;++k){
            int x=A[j+k],y=mul(O[k],A[j+k+mid]);
            A[j+k]=add(x,y),A[j+k+mid]=dec(x,y);
        }
    }if(ty==-1)for(R int i=0,inv=ksm(lim,P-2);i<lim;++i)A[i]=mul(A[i],inv);
}
void solve(int ql,int qr,int d){
    if(ql==qr)return (void)(A[d][0]=ql,A[d][1]=1);
    int mid=(ql+qr)>>1,lim=1,l=0;
    while(lim<=qr-ql+1)lim<<=1,++l;
    solve(ql,mid,d),solve(mid+1,qr,d+1);
    fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fp(i,mid-ql+2,lim-1)A[d][i]=0;
    fp(i,qr-mid+1,lim-1)A[d+1][i]=0;
    NTT(A[d],1,lim),NTT(A[d+1],1,lim);
    fp(i,0,lim-1)A[d][i]=mul(A[d][i],A[d+1][i]);
    NTT(A[d],-1,lim);
}
int C(int n,int m){
    int k1=1,k2=1;
    fp(i,n-m+1,n)k1=mul(k1,i);
    fp(i,1,m)k2=mul(k2,i);
    return mul(k1,ksm(k2,P-2));
}
int main(){
//  freopen("testdata.in","r",stdin);
    n=read(),a=read(),b=read();
    if(!a||!b||a+b-2>n-1)return puts("0"),0;
    if(n==1)return puts("1"),0;
    solve(0,n-2,0);
    printf("%d\n",mul(A[0][a+b-2],C(a+b-2,b-1)));
    return 0;
}

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

相关文章:

  • 我的网站搭建 (第21天) 评论功能设计
  • PHP 5.6 已结束安全支持,你升级到 PHP 7 系列了吗?
  • 企业网管用linux搭建邮件服务器为公司降本增效
  • Android基础:常见布局
  • 活佛开示小册下载
  • 在eclipse里配置Android ndk环境 适用于windows mac 和linux[转]
  • 把SOA看清楚
  • yafeilinux.com的开源项目非常好的东西
  • 从问题看本质:socket到底是什么?
  • LINQ之路 4:LINQ方法语法
  • matlab练习程序(异或分类)
  • REST构架风格介绍之二:CRUD
  • Silverlight for Windows Phone 7开发系列(4):动画开发
  • BizTalk 2013 Beta 新特性介绍
  • 剖析Elasticsearch集群系列之一:Elasticsearch的存储模型和读写操作
  • 3.7、@ResponseBody 和 @RestController
  • ComponentOne 2017 V2版本正式发布
  • HashMap ConcurrentHashMap
  • javascript面向对象之创建对象
  • Java程序员幽默爆笑锦集
  • Kibana配置logstash,报表一体化
  • LeetCode刷题——29. Divide Two Integers(Part 1靠自己)
  • Mysql5.6主从复制
  • Python_OOP
  • React Native移动开发实战-3-实现页面间的数据传递
  • Unix命令
  • vue自定义指令实现v-tap插件
  • 道格拉斯-普克 抽稀算法 附javascript实现
  • 工程优化暨babel升级小记
  • 关于使用markdown的方法(引自CSDN教程)
  • 猴子数据域名防封接口降低小说被封的风险
  • 经典排序算法及其 Java 实现
  • 手写一个CommonJS打包工具(一)
  • 一道面试题引发的“血案”
  • Semaphore
  • ​直流电和交流电有什么区别为什么这个时候又要变成直流电呢?交流转换到直流(整流器)直流变交流(逆变器)​
  • #NOIP 2014# day.1 T2 联合权值
  • (1)(1.13) SiK无线电高级配置(六)
  • (Redis使用系列) Springboot 使用redis的List数据结构实现简单的排队功能场景 九
  • (Ruby)Ubuntu12.04安装Rails环境
  • (办公)springboot配置aop处理请求.
  • (初研) Sentence-embedding fine-tune notebook
  • (二十三)Flask之高频面试点
  • (一) storm的集群安装与配置
  • .mysql secret在哪_MYSQL基本操作(上)
  • .NET开源全面方便的第三方登录组件集合 - MrHuo.OAuth
  • .NET设计模式(11):组合模式(Composite Pattern)
  • .net实现头像缩放截取功能 -----转载自accp教程网
  • .net中生成excel后调整宽度
  • @FeignClient注解,fallback和fallbackFactory
  • [ 蓝桥杯Web真题 ]-Markdown 文档解析
  • []指针
  • [2019.3.20]BZOJ4573 [Zjoi2016]大森林
  • [BZOJ1040][P2607][ZJOI2008]骑士[树形DP+基环树]
  • [C#C++]类CLASS