技术经验分享:CF223C

简介: 技术经验分享:CF223C

"

题意:给出一个数列a【n】,规定一种操作:用其前n项和s【n】覆盖a【n】,一共操作k次,输出数列a。1<=n<=2000,0<=k<=109,0<=ai<=109。

思路:首选想到用矩阵快速幂做,而且针对大数k,我设计了一种方案:储存20~229(230略>109),把k化为2进制,按位&1,是1就加上相应的2^n,很方便有木有?!无奈其复杂度是O(n3)的,当n=200时就差不多TLE了;而且也很耗空间。

由此得出结论:当对数列进行不规则变换时,用矩阵做;当进行纯洁的变换时,还是找规律吧O__O""…

最后找到的规律为:Sn=sum(Xn-i * ai),i=1<=n。Xn-i = C(k-1+n-i,k-1)。

1 // 2013-08-01 20:36:10

2 // 0KB 92ms 1060B

3 // by Siriuslzx

4 #include

5 #include [span style=""color: rgba(0, 0, 255, 1)"">string.h>

6 typedef long long LL;

7

8 const int N = 2005;

9 const int Mod = 1000000007;

10 LL a【N】,x【N】,iv【N】;

11

12 void gcd(LL a, LL b, //代码效果参考:https://v.youku.com/v_show/id_XNjQwNjg1NTY0NA==.html

LL&d, LL &x, LL &y){

13 if(!b){d = a, x = 1, y = 0;}

14 else{

15 gcd(b, a%b, d, y, x);

16 y -= x*(a/b);

17 }

18 }

19 LL inv(LL a, LL n){

20 LL d, x, y;

21 gcd(a, n, d, x, y);

22 return d == 1 ? (x+n)%n : -1;

23 }

24 void init(int n, int k){

25 x【0】 = 1;

26 for(int i = 1; i < n; i++)

27 x【i】 = x【i-1】(k-1+i)%Modiv【i】%Mod;

28 }

29

30 int main(){

31 int n,k,i,j;

32 LL sum;

33 for(i = 1; i < N; i++)

34 iv【i】 = inv(i, Mod);

35 scanf(""%d%d"",&n,&k);

36 for(i = 1; i <= n; i++)

37 scanf(""%I64d"",&a【i】);

38 // 其实当k==0时依然兼容,只是再算感觉浪费

39 if(!k){

40 for(i = 1; i < n; i++)

41 printf(""%I64d "",a【i】);

42 printf(""%I64d\n"",a【n】);

43 return 0;

44 }

45 // 后来把//代码效果参考:https://v.youku.com/v_show/id_XNjQwMDQxMDExNg==.html

中间这段掐了再交,时间还是一样的

46 init(n,k);

47 for(i = 1; i <= n; i++){

48 sum = 0;

49 for(j = 1; j <= i; j++)

50 sum = (sum + x【i-j】*a【j】%Mod)%Mod;

51 if(i != n)

52 printf(""%I64d "",sum);

53 else printf(""%I64d\n"",sum);

54 }

55 return 0;

56 }

通过做这题得到的一个结论:以1为首项的k阶等差数列,An = C(k+n-1,k)。


"
image.png
目录
打赏
0
0
0
0
44
分享
相关文章
用 AI 搭建秒杀平台后端,一周搞定所有功能(附超详细踩坑记录)
本文分享如何借助AI技术快速搭建电商秒杀平台后端。通过飞算JavaAI,从需求分析到代码生成全流程智能化,大幅提高开发效率。文章详细记录了技术栈选择(Java、Spring Boot、MySQL、Redis)、系统架构设计、缓存机制优化、数据一致性保障及测试调优等环节,解决高并发难题,助开发者高效完成秒杀平台构建并规避常见坑点。
千万级电商线上无阻塞双buffer缓冲优化ID生成机制深度解析
【11月更文挑战第30天】在千万级电商系统中,ID生成机制是核心基础设施之一。一个高效、可靠的ID生成系统对于保障系统的稳定性和性能至关重要。本文将深入探讨一种在千万级电商线上广泛应用的ID生成机制——无阻塞双buffer缓冲优化方案。本文从概述、功能点、背景、业务点、底层原理等多个维度进行解析,并通过Java语言实现多个示例,指出各自实践的优缺点。希望给需要的同学提供一些参考。
130 8
安卓scheme_url调端:在AndroidManifest.xml 中如何配置 Intent-filter?
为了使Android应用响应vivo和oppo浏览器的Deep Link或自定义scheme调用,需在`AndroidManifest.xml`中配置`intent-filter`。定义启动的Activity及其支持的scheme和host,并确保Activity可由外部应用启动。示例展示了如何配置HTTP/HTTPS及自定义scheme,以及如何通过浏览器和adb命令进行测试,确保配置正确无误。
深入浅出分布式事务:理论与实践
在数字化时代的浪潮中,分布式系统如同星辰大海般浩瀚而深邃。本文将带你航行于这片星辰大海,探索分布式事务的奥秘。我们将从事务的基本概念出发,逐步深入到分布式事务的核心机制,最后通过一个实战案例,让你亲自体验分布式事务的魅力。让我们一起揭开分布式事务的神秘面纱,领略其背后的科学与艺术。
139 1
Java构造方法重载的深入探索
Java构造方法重载的深入探索
134 0
通义听悟AI能力问题之API接口服务的潜在应用类别如何解决
通义听悟AI能力问题之API接口服务的潜在应用类别如何解决
178 0
Vue升级及版本不匹配解决_Vue packages version mismatch:
Vue升级及版本不匹配解决_Vue packages version mismatch:
277 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问