首页 > 其他分享 >集合幂级数 ln exp

集合幂级数 ln exp

时间:2024-04-17 15:16:00浏览次数:20  
标签:exp ln 幂级数 int 一维 集合

写的时候有个地方忘取模调了半天【流汗】

先和子集卷积一样处理出 size 那一维,先对集合幂级数那一维 fmt,然后在形式幂级数那一维作 \(\mathcal{O}(n^2)\) 的暴力 ln, exp。

写的时候遇到的坑点是集合幂级数那一维的范围其实是 \([0,n]\) 而不是 \([0,n-1]\)。

void fmt(int *f,int n,int op){
	for(int i=0;i<n;i++){
		if(op==1){
			for(int j=0;j<bit(n);j++)
				if(j&bit(i))
					cadd(f[j],f[j-bit(i)]);
		}
		else{
			for(int j=bit(n)-1;j>=0;j--)
				if(j&bit(i)){
					cdel(f[j],f[j-bit(i)]);
				}
		}
	}
}
void fmtln(int *f,int n){
	static int a[16][(1<<15)+10];
	for(int i=0;i<=n;i++)for(int j=0;j<bit(n);j++)a[i][j]=0;
	for(int i=0;i<bit(n);i++)a[__builtin_popcount(i)][i]=f[i];
	for(int i=0;i<=n;i++)fmt(a[i],n,1);
	for(int S=0;S<bit(n);S++){
		static int b[16];
		for(int i=0;i<n;i++){
			int s=1ll*(i+1)*a[i+1][S]%mod;
			for(int j=1;j<=i;j++)cdel(s,1ll*a[j][S]*b[i-j]%mod);
			b[i]=s;
		}
		for(int i=1;i<=n;i++)a[i][S]=1ll*b[i-1]*iv[i]%mod;
	}
	for(int i=0;i<=n;i++)fmt(a[i],n,-1);
	for(int i=0;i<bit(n);i++)f[i]=a[__builtin_popcount(i)][i];
}
void fmtexp(int *f,int n){
	static int a[16][(1<<15)+10];
	for(int i=0;i<=n;i++)for(int j=0;j<bit(n);j++)a[i][j]=0;
	for(int i=0;i<bit(n);i++)a[__builtin_popcount(i)][i]=f[i];
	for(int i=0;i<=n;i++)fmt(a[i],n,1);
	for(int S=0;S<bit(n);S++){
		static int b[16];
		for(int i=0;i<=n;i++){
			int s=0;
			if(i<n)s=1ll*(i+1)*a[i+1][S]%mod;
			for(int j=1;j<=i;j++)cadd(s,1ll*a[i-j+1][S]*(i-j+1)%mod*b[j-1]%mod*iv[j]%mod);
			b[i]=s;
		}
		for(int i=1;i<=n;i++)a[i][S]=1ll*b[i-1]*iv[i]%mod;
	}
	for(int i=0;i<=n;i++)fmt(a[i],n,-1);
	for(int i=0;i<bit(n);i++)f[i]=a[__builtin_popcount(i)][i];
}

标签:exp,ln,幂级数,int,一维,集合
From: https://www.cnblogs.com/do-while-true/p/18140667

相关文章

  • DevExpress使用方法GridControl总结 (转)
    DevExpress使用方法GridControl总结1.隐藏最上面的GroupPanel gridView1.OptionsView.ShowGroupPanel=false; 2.得到当前选定记录某字段的值 sValue=Table.Rows[gridView1.FocusedRowHandle][FieldName].ToString();3.数据只读 gridView1.OptionsBehavior.Edit......
  • 37、Tomato(VulnHub)
    Tomato一、nmap2211是ssh的端口,21的ftp也不是弱密码二、web渗透随便看看目录爆破/seclists/Discovery/Web-Content/common.txt/antibot_image/antibots/readme.txt发现该站点存在反爬机制/antibot_image/antibots/info.php提示我们该网页存在个参数GET:image......
  • mybtais-plus报错BuilderException: Error evaluating expression 'ew.sqlSegment !=
    在学习项目时,出现了这个报错,几经排查,发现原因:我这里是因为使用了LambdaQuery方法,不知为何就出现了冲突,导致错误,代码如下:@OverridepublicCommonUserfindByOpenId(StringopenId){returnlambdaQuery().eq(CommonUser::getOpenId,openId).one();控制台也提示到了这里有问......
  • 界面控件DevExpress Blazor UI v23.2 - 浅谈增强的可访问性
    DevExpress BlazorUI组件库提供了一套全面的原生Blazor组件(包括DataGrid、PivotGrid、调度程序、图表、数据编辑器和报表),使用C#为BlazorServer和BlazorWebAssembly创建高影响力的用户体验!获取DevExpressv23.2正式版下载DevExpress技术交流群10:532598169      欢迎......
  • mysql Explan命令 如何分析语句
    MySQL中的EXPLAIN命令是一种用于分析查询语句执行计划的强大工具,它可以帮助您了解MySQL优化器如何处理SQL查询,揭示查询执行过程中的关键细节,如表的读取顺序、数据读取操作的操作类型、所使用的索引等。通过EXPLAIN分析查询语句,您可以找出潜在的性能瓶颈,进行针对性的......
  • web表格导出插件-bootstrap-table-export
    web表格导出插件-bootstrap-table-export<html><linkhref="https://unpkg.com/[email protected]/dist/bootstrap-table.min.css"rel="stylesheet"><linkrel="stylesheet"href="https://maxcdn.bootstrapcdn.com/boo......
  • 界面组件DevExpress WinForms v23.2 - 数据展示、UI模板功能全新升级
    DevExpressWinForms拥有180+组件和UI库,能为WindowsForms平台创建具有影响力的业务解决方案。DevExpressWinForms能完美构建流畅、美观且易于使用的应用程序,无论是Office风格的界面,还是分析处理大批量的业务数据,它都能轻松胜任!DevExpressWinForms控件日前正式发布了v23.2,此版......
  • k8s之ExternalName使用
    一、简介externalNameService是k8s中一个特殊的service类型,它不需要指定selector去选择哪些pods实例提供服务,而是使用DNSCNAME机制把自己CNAME到你指定的另外一个域名上,你可以提供集群内的名字,比如mysql.db.svc这样的建立在db命名空间内的mysql服务,也可以指定http://mysql.exam......
  • 扩展中国剩余定理证明及例题 Strange Way to Express Integers
    前置知识中国剩余定理(CRT),逆元;EXCRT是什么我们知道对于\[\begin{equation} \begin{cases} x\equivc_1\(mod\m_1)\\ x\equivc_2\(mod\m_2)\\ .\\ .\\ .\\ x\equivc_i\(mod\\m_i)\\ \end{cases}\end{equation}\]一个一元线性同余方......
  • VMware 和 Oracle VM VirtualBox 网络互通(kali 与 vulnhub靶机 互通)
    由于有些从vulnhub下载的虚拟机只能用VirtualBox打开,而kali又在VMware上,两台虚拟机属于不同网段,即便同一网段也会存在无法上网的问题。在此记录一下解决方法首先查看kali(VMWare)与靶机(OracleVMVirtualBox)的IPkaliIP:192.168.198.128/24靶机IP:192.168.56.103/24(靶......