首页 > 其他分享 >《AT_arc106_d》 解题报告

《AT_arc106_d》 解题报告

时间:2023-08-29 20:23:36浏览次数:42  
标签:le limits 报告 int arc106 sum 解题 MAXN aligned

来一道简单数论。

求 \(\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^x\) ,其中 \(1\le x\le k\)

\(n\le 2e5,k\le 300\)

显然是一个 \(O(nk)\) 的做法

我们来推式子

\[\begin{aligned} \sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^x&=\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}\sum\limits_{i=0}^xC_{x}^ia_l^ia_r^{x-i} \\ &=\sum\limits_{i=0}^xC_{x}^i\sum\limits_{l=1}^{n-1}(a_l^i)\sum\limits_{r=l+1}^{n}(a_r^{x-i}) \end{aligned}\]

左边中间的式子都可以直接处理出来,但是右边的却难以处理,因为他和 \(l\) 有关,有什么办法呢。

考虑容斥。

\[\begin{aligned} \sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^x&=\frac {\sum\limits_{l=1}^{n-1}\sum\limits_{r=1}^{n}(a_l+a_r)^x-\sum\limits_{i=1}^n(2a_i)^x}2 \end{aligned}\]

也就是说我们再来推 \(\sum\limits_{l=1}^{n-1}\sum\limits_{r=1}^{n}(a_l+a_r)^x\) 这个式子。

可以得到

\(\sum\limits_{i=0}^xC_{x}^i\sum\limits_{l=1}^{n-1}(a_l^i)\sum\limits_{r=1}^{n}(a_r^{x-i})\)

然后都可以通过预处理得到

时间复杂度 \(O(nk)\)

启发:

对于一些求和式,有时候可以改变求和式的位置,说不定更容易分析题目。

点击查看代码
#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=2e5+10,MODD=998244353;
int n,k;
int a[MAXN],sum[MAXN][310];
LL ans[MAXN],C[310][310];
void init() {
	C[0][0]=1;
	for(int i=1;i<=300;++i) {
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;++j) {
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MODD;
		}
	}
}
LL ksm(LL x,LL y) {
	LL ret=1;
	while(y) {
		if(y&1) ret=ret*x%MODD;
		x=x*x%MODD;
		y>>=1;
	}
	return ret;
}
int main () {
	init();
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;++i) {
		int ls=1;
		for(int j=0;j<=k;++j) {
			sum[i][j]=(sum[i-1][j]+ls)%MODD;
			ls=((LL)ls*a[i])%MODD;
		}
	}
	for(int i=1;i<=n;++i) {
		LL pp=1;
		for(int j=0;j<=k;++j) {
			ans[j]=(ans[j]-pp+MODD)%MODD;
			pp=pp*2*a[i]%MODD;
		}
	}
	for(int i=0;i<=k;++i) {
		for(int j=0;j<=i;++j) {
			ans[i]=(ans[i]+(LL)sum[n][j]*sum[n][i-j]%MODD*C[i][j]%MODD)%MODD;
		}
	}
	LL i2=ksm(2,MODD-2);
	for(int i=1;i<=k;++i) {
		printf("%lld\n",ans[i]*i2%MODD);
	} 
	return 0;
}

标签:le,limits,报告,int,arc106,sum,解题,MAXN,aligned
From: https://www.cnblogs.com/ddl1no2home/p/17665744.html

相关文章

  • The 2021 ICPC Asia Shenyang Regional Contest 解题报告
    The2021ICPCAsiaShenyangRegionalContestsolo七题罚时738打到金尾了,但是这个G和I也应该是自己能做出来的。G找了若干性质确实转化到最后一步了。但本应该搞出的dp没有想到。G和M感觉都有点降智。而I则是被复数吓到了。有点菜。B:拆位,扩展域并查集。E:签到。F......
  • RASP分析报告
    RASP原理RASP(RuntimeApplicationSelf-Protection,运行时应用自我保护)是一种应用安全保护机制,它的目标是在应用程序运行时检测和防御各种安全攻击。与传统的防护机制(例如防火墙和安全软件)不同,RASP在应用程序内部嵌入了安全保护功能,可以实时监测和保护应用程序免受攻击。随着Web应......
  • 电动牙刷上架亚马逊美国站UL4131测试报告
    在我们的日常生活中,电动牙刷已经成为了许多人日常清洁牙齿的必备工具。然而,在将其推向市场的过程中,制造商们必须遵守一系列的法规和标准,以确保产品的安全性和质量。这其中就包括了我们今天要讨论的UL4131标准。UL4131标准是一款关于个人保健电器类的产品安全标准,它主要关注的是个人......
  • 陶瓷红外线加热器行业市场调查趋势分析报告2023-2029
    2023-2029全球陶瓷红外线加热器行业调研及趋势分析报告2022年全球陶瓷红外线加热器市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国陶瓷红外线加热器市场占据全球约%的市场份......
  • 智能存储控制器行业市场调查趋势分析报告2023-2029
    2023-2029全球智能存储控制器行业调研及趋势分析报告2022年全球智能存储控制器市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国智能存储控制器市场占据全球约%的市场份额,为全......
  • 便携式电源轨探头行业市场调查趋势分析报告2023-2029
    2023-2029全球便携式电源轨探头行业调研及趋势分析报告2022年全球便携式电源轨探头市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国便携式电源轨探头市场占据全球约%的市场份......
  • 粉状聚合物分散剂行业市场调查趋势分析报告2023-2029
    2023-2029全球粉状聚合物分散剂行业调研及趋势分析报告2022年全球粉状聚合物分散剂市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国粉状聚合物分散剂市场占据全球约%的市场份......
  • Atcoder Beginner Contest 317 解题报告
    AtcoderBeginnerContest317ABC316咋没了。暂时A~E。HintsD$\quad$可以算出每次选举需要的改票数。然后变成了一个经典问题。E$\quad$有点naive。不用担心暴力扫T掉,时间复杂度是真的。F$\quad$F1$\qquadn$这么大一维都枚举不了……诶,$a_i$只有$10$?$\qua......
  • 【专题】2022品牌营销决策解决方案报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33511根据报告合集显示,在消费者的亲友分享、社交平台、订单评价等环节,00后表现出活跃的参与度,而90后和95后在部分环节也较为活跃。相比之下,70后和80后在分享中的参与度最低,主要以亲友分享为主。阅读原文,获取专题报告合集全文,解锁文末335份品牌营销......
  • 【专题】2023品牌内容营销洞察报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33511根据报告合集显示,在消费者的亲友分享、社交平台、订单评价等环节,00后表现出活跃的参与度,而90后和95后在部分环节也较为活跃。相比之下,70后和80后在分享中的参与度最低,主要以亲友分享为主。阅读原文,获取专题报告合集全文,解锁文末335份品牌营销......