【洛谷7016】[CERC2013] Captain Obvious and the Rabbit-Man(手动高斯消元)
2021/5/31 18:21:12
本文主要是介绍【洛谷7016】[CERC2013] Captain Obvious and the Rabbit-Man(手动高斯消元),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
点此看题面
- 设\(p_i=\sum_{j=1}^na_jFib_j^i\),给定\(n\)和\(p_{1\sim n}\),求\(p_{n+1}\)。
- \(n\le4\times10^3\)
手动高斯消元
发现这道题中有\(n\)个未知数\(a_{1\sim n}\),然后\(p_{1\sim n}\)就相当于是\(n\)个方程,因此容易想到高斯消元,但\(O(n^3)\)的一般高斯消元显然无法通过此题。
要是真想把这\(n\)个未知数全部解出来肯定没有优化的余地,因此下面先来一步转化:
我们在最后添上\(p_{n+1}\)这个方程(等号右边的值先定为\(0\))和前面的方程一起消元,发现在前\(n\)个方程消元结束后\(p_{n+1}\)的所有未知数都被消干净了,因此等号右边值的相反数就是\(p_{n+1}\)了。
接下来就可以开始优化高斯消元了。
考虑我们要消去第\(i\)行之后所有行第\(i\)列的值,一般的做法是枚举第\(i\)行从之后的每一行中消去。这样一来后面的列都被减得乱七八糟了,毫无规律可言,完全没有用到系数的性质。
因此我们要换一种消元的思路:第\(i\)次消元的时候从后往前枚举每一行,减去上一行\(\times Fib_i\)。
注意到这里我们相当于根据系数给这个方程组进行了一个手动高斯消元,因此不用再管系数的修改,而只需考虑等号右边值之间的运算,复杂度就是\(O(n^2)\)的了。
代码:\(O(n^2)\)
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 4000 using namespace std; int n,X,a[N+5],Fib[N+5]; int main() { RI Tt,i,j;scanf("%d",&Tt);W(Tt--) { for(scanf("%d%d",&n,&X),i=1;i<=n;++i) scanf("%d",a+i),Fib[i]=i<=2?i:(Fib[i-2]+Fib[i-1])%X;//预处理斐波那契数 for(a[n+1]=0,i=1;i<=n;++i) for(j=n+1;j^i;--j) a[j]=(a[j]-1LL*a[j-1]*Fib[i]%X+X)%X;//手动高斯消元 printf("%d\n",(X-a[n+1])%X);//第n+1个方程等号右边值的相反数 }return 0; }
这篇关于【洛谷7016】[CERC2013] Captain Obvious and the Rabbit-Man(手动高斯消元)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享