13.P1707 刷题比赛

阅读数: 次 2020-11-23

字数：825字 | 预计阅读时长：4分钟

作者：冰糖鸽子

题目来源-luogu

~~我还没怎么见过直接说要用什么算法的题呢~~

矩阵乘法，矩阵快速幂什么的不再多说，上OI-wiki

Link

放几道练习题(循序渐进)：

按照惯例，推转移矩阵。

三个式子前面的 $pa_{k+1}$ 这种都比较容易分解，因为式子已经在题目里了，其余的项难分解的基本如下两种：

$(k+1)^2 = (k+1) \times (k+1) = k^2 + 2k + 1$
$z^{k+1} = z^k \times z$

然后就可以推出来一个维护 $11$ 个值的矩阵(空白处为 $0$ )：

	$A_i$	$B_i$	$C_i$	$A_{i+1}$	$B_{i+1}$	$C_{i+1}$	$i$	$i^2$	$1$	$w^k$	$z^k$
$A_{i+1}$				1
$B_{i+1}$					1
$C_{i+1}$						1
$A_{i+2}$	q			p	1	1	t	r	1
$B_{i+2}$		v		1	u	1				1
$C_{i+2}$			y	1	1	x	1		2		1
$i+1$							1		1
${i+1}^2$							2	1	1
$1$									1
$w^{i+1}$										w
$z^{i+1}$											z

然后将 lot 矩阵设为以上矩阵：

lot.m[0][3]=lot.m[1][4]=lot.m[2][5]=lot.m[3][4]=lot.m[3][5]=lot.m[3][8]=lot.m[4][3]=lot.m[4][5]=lot.m[4][9]=lot.m[5][3]=lot.m[5][4]=lot.m[5][6]=lot.m[5][10]=lot.m[6][6]=lot.m[6][8]=lot.m[7][7]=lot.m[7][8]=lot.m[8][8]=1;//所有为1的格
lot.m[5][8]=lot.m[7][6]=2;//所有为2的格
lot.m[3][0]=q;lot.m[3][3]=p;lot.m[3][6]=t;lot.m[3][7]=r;//与求A数列相关的格
lot.m[4][1]=v;lot.m[4][4]=u;lot.m[9][9]=w;//与求B数列相关的格
lot.m[5][2]=y;lot.m[5][5]=x;lot.m[10][10]=z;//与求C数列相关的格

之后是普通的矩阵快速幂，注意进行矩阵乘法需要使用龟速乘防爆

龟速乘

int mut_q(int a,int b)
{
	int ans=0;
	while(b!=0)
	{
		if(b%2==1){ans=(ans+a)%pp;}
		a=(a*2)%pp;
		b/=2;
	}
	return ans;
}
node do_mut(node a,node b)
{
	node ans;
	memset(ans.m,0,sizeof(ans.m));
	for(int i=0;i<11;i++)
	{
		for(int j=0;j<11;j++)
		{
			for(int k=0;k<11;k++)
			{
				ans.m[i][j]+=mut_q((a.m[i][k]%pp),(b.m[k][j]%pp))%pp;ans.m[i][j]%=pp;
			}
		}
	}
	return ans;
}
void done(int x)
{
	while(x)
	{
		if(x&1)
		{
			one=do_mut(one,lot);
		}
		lot=do_mut(lot,lot);
		x>>=1;
	}
}

最后一个问题：如何求答案

~~其实这个明明很明显的嘛，不多说了~~

第四行，第五行，第六行分别对应 nodgd,Ciocio,Nicole ,把这三行分别乘上基础数列(如下)，再膜一下，就是每个人的答案了

$$ 1 ,1,1,3,3,3,1,1,1,w,z $$

(对应上文表格的11项)

本部分代码：

int sumA=0,sumB=0,sumC=0;
for(int i=0;i<11;i++)
{
	sumA+=one.m[3][i]*doit[i];sumA%=pp;
	sumB+=one.m[4][i]*doit[i];sumB%=pp;
	sumC+=one.m[5][i]*doit[i];sumC%=pp;
}
cout<<"nodgd "<<sumA<<endl;
cout<<"Ciocio "<<sumB<<endl;
cout<<"Nicole "<<sumC<<endl;

本文作者： 益题 Yitee
发布时间： 2020-11-23
最后更新： 2021-08-19
本文标题： 13.P1707 刷题比赛
本文链接： https://yitee.top/posts/41069.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！