首页 > 其他分享 >Luogu P5173 传球

Luogu P5173 传球

时间：2024-02-05 10:37:14浏览次数：29  
标签：传球 int Luogu 复杂度 矩阵 3505 long P5173 cdots

题目传送门

SubTask \(1.1\)，8 pts

首先，我们可以推出一个极为简单的 dp 转移方程：

\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1} \]

\(f_{i,j}\) 表示当前秒数为 \(i\)，球在 \(j\) 手上的方案数量。

时间复杂度/空间复杂度：\(O(nm)\)，肯定不能通过此题。

其实这个就是 P1057 NOIP2008 普及组 传球游戏 的做法。

SubTask \(1.2\)，8 pts，矩阵快速幂优化

为什么还是 8pts？因为矩阵快速幂优化后复杂度也只能过 \(8\%\) 的数据。

dp 的复杂度太高，我们都学过矩阵快速幂，它可以优化数列；

所以我们可以采用矩阵快速幂优化这个 dp 过程。

首先我们需要构造一个矩阵 \(A\)，用来加速数列。

我们的初始矩阵：

\[Ans = \begin{bmatrix} a_{i-1,1}\\ a_{i-1,2}\\ a_{i-1,3}\\ \cdots\\ a_{i-1,1}\\ \end{bmatrix} \]

我们转移的目标矩阵：

\[Ans = \begin{bmatrix} a_{i,1}\\ a_{i,2}\\ a_{i,3}\\ \cdots\\ a_{i,1}\\ \end{bmatrix} \]

由于我们推出的dp式子为：每一个人从上一秒的相邻两个人转移，所以 \(A\)是：

\[A = \begin{bmatrix} 0&1&0&0&\cdots&0&1\\ 1&0&1&0&\cdots&0&0\\ 0&1&0&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 1&0&0&0&\cdots&1&0\\ \end{bmatrix} \]

关于矩阵乘法，这里不再赘述。

时间复杂度：\(O(n^3\log{m})\)

SubTask \(2\)，32 pts，时间复杂度优化

我们观察，发现 \(A\) 矩阵是循环的，每一行是上一行每一项右移一位（最后移到第一位）。

那么，我们就可以用快速幂把一行乘出来，然后再移出其他行。

关于累乘答案时，因为我们的 \(Ans\) 矩阵只有一行有数，其他行都是占位符，可以全部优化掉，只乘第一行。

这样，时间复杂度可以压到 \(O(n^2\log{m})\)。

int n, m;
const int MOD=1e9+7;
long long a[1005][1005], ans[1005][1005];
void Matrix1(){  
	long long c[1005][1005]={0};
	for (int j=1; j<=n; j++){
		for (int k=1; k<=n; k++){
			c[1][j]+=(a[1][k]*a[k][j])%MOD;
			c[1][j]%=MOD;
		}
	}
	for (int i=2; i<=n; i++){
		c[i][1]=c[i-1][n];
		for (int j=2; j<=n; j++){
			c[i][j]=c[i-1][j-1];
		}
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			a[i][j]=c[i][j];
		}
	}
}
void Matrix2(){
	long long c[1005][1005]={0};
	for (int j=1; j<=n; j++){
		for (int k=1; k<=n; k++){
			c[1][j]+=(ans[k][1]*a[j][k])%MOD;
			c[1][j]%=MOD;
		}
	}
	for (int i=1; i<=n; i++){
		ans[i][1]=c[1][i];
	}
}

SubTask \(3\)，64 pts(O2)，空间优化

虽然上面的时间复杂度理论上可以通过本题，但是空间绝对不允许。

空间 32MB，无论怎么样都得 MLE 送走。

还是利用上面那个原理，由于 \(A\) 矩阵循环，可以只存一行，等到累乘答案再把其他行算出来。

至于 \(A\) 矩阵自乘，也是同理。先存一行，每一次往下右移一次，即可。

还有 \(Ans\) 矩阵，本身就只有一行有数据，可以直接压掉其他行。

时间复杂度：\(O(n^2\log{m})\)

空间复杂度：\(O(n)\)

void Matrix1(){  
	long long c[3505]={0}, d[3505]={0};  //新开一个数组，用来存每次右移后的a[];
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=n; j++){
		for (int k=1; k<=n; k++){
			c[j]=(c[j]+a[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=n; i++) a[i]=c[i];
}
void Matrix2(){
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=n; j++){
		for (int k=1; k<=n; k++){
			c[j]=(c[j]+ans[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=n; i++) ans[i]=c[i];
}

SubTask \(4\)，72 pts(O2)，常数优化Part.1

虽然时间和空间如上所说，理论上可以通过本题，但你会发现，还是过不了( TLE )。

如果你仔细计算，你会发现时间复杂度大约为 \(7.35\times10^8\)，显然无法通过本题 1s 的限制。所以，我们要想办法优化这份代码。

仔细观察每一行，你会发现以下现象：

当 \(n\) 为奇数，\(A\) 矩阵一行为：

\[\begin{matrix} a_1&a_2&a_3&\cdots&a_{\lfloor\frac{n+1}{2}\rfloor-1}&a_{\lfloor\frac{n+1}{2}\rfloor}&a_{\lfloor\frac{n+1}{2}\rfloor-1}&\cdots&a_4&a_3&a_2\\ \end{matrix} \]

当 \(n\) 为偶数，\(A\) 矩阵一行为：

\[\begin{matrix} a_1&a_2&a_3&\cdots&a_{\lfloor\frac{n}{2}\rfloor}&a_{\lfloor\frac{n}{2}\rfloor+1}&a_{\lfloor\frac{n}{2}\rfloor}&\cdots&a_4&a_3&a_2\\ \end{matrix} \]

所以，我们只需要求出 \(A\) 矩阵一行的一半，然后再复制出来。

void Matrix1(){  //当n为奇数
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=(n+1)/2; j++){
		for (int k=1; k<=n; k++){
			c[j]=(c[j]+a[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=(n+1)/2; i++) a[i]=c[i];
	for (int i=(n+1)/2+1; i<=n; i++) a[i]=c[n-i+2];
//	for (int i=1; i<=n; i++) printf("%lld ", a[i]);
//	puts("");
}
void Matrix3(){  //当n为偶数
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=n/2+1; j++){
		for (int k=1; k<=n; k++){
			c[j]=(c[j]+a[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=n/2+1; i++) a[i]=c[i];
	for (int i=n/2+2; i<=n; i++) a[i]=c[n-i+2];
}
void Matrix2(){ //不变
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=n; j++){
		for (int k=1; k<=n; k++){
			c[j]=(c[j]+ans[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=n; i++) ans[i]=c[i];
}

SubTask \(5\)，84 pts(O2)，常数优化Part.2

然后，还是 TLE。

为什么？因为 \(3.5\times10^8\) 的复杂度显然还无法通过1s的时限。

所以我们继续优化。

我们都知道，计算机做取模运算做得很慢。而当我们观察矩阵快速幂的计算过程，我们又会发现：但凡 \(A\) 或 \(Ans\) 矩阵中有一个数为 \(0\)，本次乘法与取模无意义。

所以我们遇到这种情况，直接 continue。

不过说来也玄学，这样一个 continue 居然优化了 12pts。

void Matrix1(){  
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=(n+1)/2; j++){
		for (int k=1; k<=n; k++){
			if(a[k]==0||d[k]==0) continue; //当乘法有0，跳过
			c[j]=(c[j]+a[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=(n+1)/2; i++) a[i]=c[i];
	for (int i=(n+1)/2+1; i<=n; i++) a[i]=c[n-i+2];
//	for (int i=1; i<=n; i++) printf("%lld ", a[i]);
//	puts("");
}
void Matrix3(){  
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=n/2+1; j++){
		for (int k=1; k<=n; k++){
			if(a[k]==0||d[k]==0) continue;
			c[j]=(c[j]+a[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=n/2+1; i++) a[i]=c[i];
	for (int i=n/2+2; i<=n; i++) a[i]=c[n-i+2];
}
void Matrix2(){
	long long c[3505]={0}, d[3505]={0};
	for (int i=1; i<=n; i++) d[i]=a[i];
	for (int j=1; j<=n; j++){
		for (int k=1; k<=n; k++){
			if(ans[k]==0||d[k]==0) continue;
			c[j]=(c[j]+ans[k]*d[k])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; k++) d[k]=d[k+1];
		d[n]=w;
	}
	for (int i=1; i<=n; i++) ans[i]=c[i];
}

SubTask \(6\) ，92 pts(O2)，常数优化 Part.3

但还是 TLE 啊啊啊！！！

所以我们还需要优化一下。

我们注意到，虽然我们执行了 continue 语句，但每一次循环还需要时间。这里的时间肯定也浪费了。

所以我们新开一个数组 \(CNT\) ，记录每一个相乘中有贡献的下标。

然后循环的时候，就可以 for (int k=1; k<=cnt; ++k) 来优化时间了。

时间复杂度：\(O(n^2\log{m})\) （由于每次 \(A\) 矩阵右移还是 \(O(n)\) 的）

inline void Matrix1(){
	cnt=0;
	memset(c, 0, sizeof c);
	for (int i=1; i<=n; i++){
		d[i]=a[i];
		if(a[i]) e[++cnt]=i;
	}
	for (int j=1; j<=(n+1)/2; ++j){
		for (int k=1; k<=cnt; ++k){
			c[j]=(c[j]+a[e[k]]*d[e[k]])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; ++k) d[k]=d[k+1];
		d[n]=w;
		for (int i=1; i<=cnt; ++i){
			e[i]--;
			if(e[i]<1) e[i]=n;
		}
	}
	for (int i=1; i<=(n+1)/2; ++i) a[i]=c[i];
	for (int i=(n+1)/2+1; i<=n; ++i) a[i]=c[n-i+2];
}
inline void Matrix3(){  
	cnt=0;
	memset(c, 0, sizeof c);
	for (int i=1; i<=n; ++i){
		d[i]=a[i];
		if(a[i]) e[++cnt]=i;
	}
	for (int j=1; j<=n/2+1; ++j){
		for (int k=1; k<=cnt; ++k){
			c[j]=(c[j]+a[e[k]]*d[e[k]])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; ++k) d[k]=d[k+1];
		d[n]=w;
		for (int i=1; i<=cnt; ++i){
			e[i]--;
			if(e[i]<1) e[i]=n;
		}
	}
	for (int i=1; i<=n/2+1; ++i) a[i]=c[i];
	for (int i=n/2+2; i<=n; ++i) a[i]=c[n-i+2];
}
inline void Matrix2(){
	memset(c, 0, sizeof c);
	cnt=0;
	for (int i=1; i<=n; ++i){
		d[i]=a[i];
		if(a[i]) e[++cnt]=i;
	} 
	for (int j=1; j<=n; ++j){
		for (int k=1; k<=cnt; ++k){ //只有e[k]中出现的值才有贡献，其他无效 
			c[j]=(c[j]+ans[e[k]]*d[e[k]])%MOD;
		}
		int w=d[1];
		for (int k=1; k<n; ++k) d[k]=d[k+1];
		for (int i=1; i<=cnt; ++i){
			e[i]--;
			if(e[i]<1) e[i]=n;
		}
		d[n]=w;
	}
	for (int i=1; i<=n; ++i) ans[i]=c[i];
}

SubTask \(7\)，100 pts(O2)，常数优化Part.4

还是 TLE 了两个点。

只能对右移操作下手了。

既然只有在 \(A\) 矩阵中的非零数才对答案有贡献，那我们在存右移的时候也可以只存这些点啊！

所以，整个右移操作被优化掉。（因为 \(A\) 自乘的时候一个数组是有贡献的值，另一个存的是下标， \(Ans\) 数组同理）

AC Code:

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
int n, m, cnt, e[3505];
const int MOD=1e9+7;
long long c[3505], a[3505], ans[3505], d[3505];
inline void Matrix1(){
	cnt=0;
	memset(c, 0, sizeof c);
	for (int i=1; i<=n; i++){
		if(a[i]) e[++cnt]=i, d[cnt]=a[i];
	}
	int u=(n+1)/2;
	for (int j=1; j<=u; ++j){
		for (int k=1; k<=cnt; ++k){
			c[j]=(c[j]+a[e[k]]*d[k])%MOD;
		}
		for (int i=1; i<=cnt; ++i){
			e[i]--;
			if(e[i]<1) e[i]=n;
		}
	}
	for (int i=1; i<=u; ++i) a[i]=c[i];
	for (int i=u+1; i<=n; ++i) a[i]=c[n-i+2];
}
inline void Matrix3(){  
	cnt=0;
	memset(c, 0, sizeof c);
	for (int i=1; i<=n; ++i){
		if(a[i]) d[++cnt]=a[i], e[cnt]=i;
	}
	int u=n/2+1;
	for (int j=1; j<=u; ++j){
		for (int k=1; k<=cnt; ++k){
			c[j]=(c[j]+a[e[k]]*d[k])%MOD;
		}
		for (int i=1; i<=cnt; ++i){
			e[i]--;
			if(e[i]<1) e[i]=n;
		}
	}
	for (int i=1; i<=u; ++i) a[i]=c[i];
	for (int i=u+1; i<=n; ++i) a[i]=c[n-i+2];
}
inline void Matrix2(){
	memset(c, 0, sizeof c);
	cnt=0;
	for (int i=1; i<=n; ++i){
		
		if(a[i])e[++cnt]=i, d[cnt]=a[i];
	}
	for (int j=1; j<=n; ++j){
		for (int k=1; k<=cnt; ++k){
			c[j]=(c[j]+ans[e[k]]*d[k])%MOD;
		}
		for (int i=1; i<=cnt; ++i){
			e[i]--;
			if(e[i]<1) e[i]=n;
		}
	}
	for (int i=1; i<=n; ++i) ans[i]=c[i];
}
int main(){
	scanf("%d%d", &n, &m);
	ans[1]=a[n]=a[2]=1;
	for (;m;){
		if(m&1) Matrix2();
		n&1?Matrix1():Matrix3();
		m>>=1;
	}
	printf("%lld\n", ans[1]);
	
	return 0;
}

标签：传球,int,Luogu,复杂度,矩阵,3505,long,P5173,cdots
From： https://www.cnblogs.com/ylc666/p/18007478

相关文章

  • Luogu「Daily OI Round 3」Simple 题解
    #include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cstring>#include<string>#include<string.h>#include<vector>#defineintlonglong#definerep(a,b,c)for(autoa=b;a......
  • luogu P2967 [USACO09DEC] Video Game Troubles G
    CSPRP++这道题就是一个背包升级的板子，我不会告诉你，这题我用了半个小时才做完本题的思路是：第一步：先忽略第$i$台主机的价格，只对第$i$款游戏的$G_{i}$款游戏做01背包，此时得到的$f[i][j]$为从前$i$台主机中花费了$j$元购买游戏得到的伪收益。第二步：再考虑第$i$......
  • Luogu P1104 生日
    link生日题目描述cjf君想调查学校OI组每个同学的生日，并按照年龄从大到小的顺序排序。但cjf君最近作业很多，没有时间，所以请你帮她排序。输入格式输入共有\(n+1\)行，第\(1\)行为OI组总人数\(n\)；第\(2\)行至第\(n+1\)行分别是每人的姓名\(s\)、出生年\(y\)......
  • Luogu P1923 求第 k 小的数
    link求第k小的数题目描述输入\(n\)（\(1\len<5000000\)且\(n\)为奇数）个数字\(a_i\)（\(1\lea_i<{10}^9\)），输出这些数字的第\(k\)小的数。最小的数是第\(0\)小。请尽量不要使用nth_element来写本题，因为本题的重点在于练习分治算法。输入格式无输出格式无......
  • Luogu P1249 最大乘积
    最大乘积题目描述一个正整数一般可以分为几个互不相同的自然数的和，如\(3=1+2\)，\(4=1+3\)，\(5＝1+4=2+3\)，\(6=1+5＝2+4\)。现在你的任务是将指定的正整数\(n\)分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。输入格式只一个正整数\(n\)，（\(3\leqn\leq10000\)）。......
  • Luogu P1518 [USACO2.4] 两只塔姆沃斯牛
    [USACO2.4]两只塔姆沃斯牛TheTamworthTwo\(\color{cyan}link\)题目描述两只牛逃跑到了森林里。FarmerJohn开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为（牛和John）。追击在\(10\times10\)的平面网格内进行。一个格子可以是：一个障碍物，两头牛（它们总在一......
  • Luogu P4924 [1007] 魔法少女小Scarlet
    [1007]魔法少女小Scarlet\(\color{cyan}link\)题目描述Scarlet最近学会了一个数组魔法，她会在\(n\timesn\)二维数组上将一个奇数阶方阵按照顺时针或者逆时针旋转\(90^\circ\)。首先，Scarlet会把\(1\)到\(n^2\)的正整数按照从左往右，从上至下的顺序填入初始的二维数组......
  • Luogu P1563 [NOIP2016 提高组] 玩具谜题
    [NOIP2016提高组]玩具谜题\(link\)题目背景NOIP2016提高组D1T1题目描述小南有一套可爱的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：这时singer告诉小南一个谜题：“......
  • Luogu P1042 [NOIP2003 普及组] 乒乓球
    [NOIP2003普及组]乒乓球\(link\)题目背景国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中\(11\)分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图......
  • 玩玩luogu算法题——第1期
    昨天已经把所有大作业写完了，所以今天就想去做一些有趣的事情...今天做的题都不是特别难，除了最后一题（写了大概1000多行Markdown，结果能Accepted的代码居然只有十几行？！）目标：希望暑假的时候每天都能更新一点算法题的随笔出来，加油~P1000超级玛丽游戏（一个非常入门的题目，作用是用来快速......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99