se3948_30.03.23

se3948_30.03.23题目描述题解好仙的题啊考虑设交集大小至少为xxx的个数为axa_xax​,则ax=(xn)(22n−x−1)a_x=(_x^n)(2^{2^{n-x}}-1)ax​=(xn​)(22n−x−1)然后我们考虑构造容斥系数fxf_xfx​,使得ans=∑x=0nfxaxans=\sum_{x=0}^nf_xa_xans=∑x=0n​fx​ax​然后我们考虑到如果交集大小恰好为…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

题目描述

为了抵御以尼古拉奥尔丁为首的上古龙族的入侵,地球的守护者 Yopilla 集齐了 n n n 种人类文明的本源力量 —— 世界之力。

Yopilla 打算使用若干种技能来对抗尼古拉奥尔丁的进攻。每种技能由若干种世界之力构成。换句话说,一共有 2 n 2 ^ n 2n 种技能,Yopilla 要使用若干种技能来对抗尼古拉奥尔丁。

大战前夕,Yopilla 走在波士顿的街头,突然看见天空中飞过了 4 4 4 只白鸽,他便洞察了战胜尼古拉奥尔丁的秘密:只要他使用的技能中,都含有的世界之力的种类数恰好为 4 4 4 的倍数,他便可以打败敌人。

Yopilla 想知道,他有多少种使用技能的情况,能战胜敌人。请你替 Yopilla 回答这个问题,答案对 998244353 998244353 998244353 取模即可。

题解

好仙的题啊

考虑设交集大小至少为 x x x 的个数为 a x a_x ax ,则 a x = ( x n ) ( 2 2 n − x − 1 ) a_x=(_x^n)(2^{2^{n-x}}-1) ax=(xn)(22nx1)

然后我们考虑构造容斥系数 f x f_x fx ,使得 a n s = ∑ x = 0 n f x a x ans=\sum_{x=0}^nf_xa_x ans=x=0nfxax

然后我们考虑到如果交集大小恰好为 x x x 的最终要被算 [ x % 4 = 0 ] [x\%4=0] [x%4=0] 遍,而对于 ≤ x \le x x i i i ,它对于 x x x 的贡献就是 ( i x ) (_i^x) (ix) ,所以我们要使得 [ x % 4 = 0 ] = ∑ k = 0 x ( k x ) f x [x\%4=0]=\sum_{k=0}^x(_k^x)f_x [x%4=0]=k=0x(kx)fx

考虑二项式反演,将式子化为 f x = ∑ k = 0 x ( − 1 ) x − k ( k x ) [ x % 4 = 0 ] f_x=\sum_{k=0}^x(-1)^{x-k}(_k^x)[x\%4=0] fx=k=0x(1)xk(kx)[x%4=0]

考虑将 [ x % 4 = 0 ] [x\%4=0] [x%4=0] 化开,这时候我们要用到很神奇的东西:单位复数根

w m w_m wm 表示主 m m m 次单位根,那么根据性质,我们可以得到 [ x % m = 0 ] = ∑ i = 0 m − 1 ( w m x ) i [x\%m=0]=\sum_{i=0}^{m-1}(w_m^x)^i [x%m=0]=i=0m1(wmx)i

于是 f x = ∑ k = 0 x ( − 1 ) x − k ( k x ) ∑ i = 0 4 − 1 ( w 4 x ) i f_x=\sum_{k=0}^x(-1)^{x-k}(_k^x)\sum_{i=0}^{4-1}(w_4^x)^i fx=k=0x(1)xk(kx)i=041(w4x)i

i i i 提前,得到 f x = ( − 1 ) x 4 ∑ i = 0 3 ( 1 − w 4 i ) x f_x=\frac{(-1)^x}{4}\sum_{i=0}^{3}(1-w_4^i)^x fx=4(1)xi=03(1w4i)x

于是我们可以 O ( n m ) O(nm) O(nm)处理出 f x f_x fx ,然后计算答案

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,P=998244353;
int n,jc[N],ny[N],w[4],W[4],f[N],s=1;
int X(int x){ 
   return x>=P?x-P:x;}
int C(int x,int y){ 
   
	return 1ll*jc[x]*ny[y]%P*ny[x-y]%P;
}
int K(int x,int y){ 
   
	int z=1;
	for (;y;y>>=1,x=1ll*x*x%P)
		if (y&1) z=1ll*z*x%P;
	return z;
}
int main(){ 
   
	cin>>n;jc[0]=1;
	for (int i=1;i<=n;i++)
		jc[i]=1ll*i*jc[i-1]%P;
	ny[n]=K(jc[n],P-2);
	for (int i=n;i;i--)
		ny[i-1]=1ll*i*ny[i]%P;
	w[0]=1;w[1]=911660635;
	for (int i=2;i<4;i++)
		w[i]=1ll*w[i-1]*w[1]%P;
	for (int i=0;i<4;i++)
		W[i]=1,w[i]=X(1+P-w[i]);
	for (int i=0,F=1;i<=n;i++,F=P-F){ 
   
		for (int j=0;j<4;j++)
			f[i]=X(f[i]+W[j]);
		f[i]=748683265ll*F%P*f[i]%P;
		for (int j=0;j<4;j++)
			W[j]=1ll*W[j]*w[j]%P;
	}
	for (int i=n,v=2,u;~i;i--)
		u=1ll*C(n,i)*X(v-1+P)%P,
		s=X(s+1ll*u*f[i]%P),v=1ll*v*v%P;
	cout<<s<<endl;return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/184479.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 360自动拦截的防护怎么修改_微信屏蔽投诉按钮代码

    360自动拦截的防护怎么修改_微信屏蔽投诉按钮代码个人有各自不同的编写方法。不必拘泥一格。只要了解原理是访问首页,运行js文件,在JS文件里面调用一个文件,显示网站。JS的写法有很多,比如还有下面的写法:document.write(unescape(unescape(unescape(unescape(unescape(‘%252525253Cframeset%2525252520rows%252525253D%2525252522*%

  • cmd命令如何切换盘符_cmd命令修改盘符

    cmd命令如何切换盘符_cmd命令修改盘符返回上一级目录:cd..进入盘符根目录(例如进入E盘): e:

  • 次世代3A游戏开发将飙至1.5亿美元,游戏时长将更短

    次世代3A游戏开发将飙至1.5亿美元,游戏时长将更短即将翻过的这个世代,是大作的时代,涌现了一大批的大作,譬如《荒野大镖客2》、《GTA5》、《巫师3》等游戏。当然也是预算高涨、不断跳票和开发商经常加班加点的时代。随着PS5和XSX即将到来,随之一起的将是有史以来细节最丰富和预算更贵的游戏世界,问题就出现了:游戏行业还会继续痴迷于这么庞大世界的游戏吗?在GameBabLive会议上,SIE前总裁ShawnLayden表达了对次世代游戏开发成本倍增的担忧。他认为次世代3A游戏的开发将不可避免地从今天的8000万美元飙升至1.5亿美元。因此Lay

  • iPhone4S iOS6.1.2完美越狱「建议收藏」

    iPhone4S iOS6.1.2完美越狱「建议收藏」iPhone4SiOS6.1.2完美越狱iOS6完美越狱工具Evasi0n继续更新至1.5版本,新版本同样支持iOS6.1.2完美越狱,并提升了设备的开机速度。如果您的设备未越狱,建议使用Evasi0n1.5进行完美越狱。如果您之前越狱后遇到了开机慢的问题,可至cydia下载0.4-1修复补丁。iOS6.x完美越狱工具下载:点击下载>>>evasi0n1.5(wind

  • allowMultiQueries=true_python的list用法

    allowMultiQueries=true_python的list用法消息列表:消息 描述 WM_NOTIFICATION_CLICKED 控件被点击 WM_NOTIFICATION_RELEASED 控件被释放 WM_NOTIFICATION_MOVED_OUT 控件被点击,指针移出控件但没被释放 WM_NOTIFICATION_SEL_CHANGED 控件选中的内容被改变 常用函数LISTWHEEL_A…

  • 视频编码技术详解

    1、引言  如今我们所处的时代,是移动互联网时代,也可以说是视频时代。从快播到抖音,从“三生三世”到“延禧攻略”,我们的生活,被越来越多的视频元素所影响。    而这一切,离不开视频拍摄技术的不断升级,还有视频制作产业的日益强大。    此外,也离不开通信技术的飞速进步。试想一下,如果还是当年的56KModem拨号,或者是2G手机,你还能享受到现在动辄10…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号