§ 题意简述

给你三个互相依赖的递推式，分别求值。

§ 题解

裸的矩阵快速幂，我们把这几个东西放进矩阵：

$$B=\begin{bmatrix} a_{k}\\ a_{k+1}\\ b_{k}\\ b_{k+1}\\ c_{k}\\ c_{k+1}\\ k^{2}\\ k\\ w^{k}\\ 2^{k}\\ 1 \end{bmatrix}$$

则初始矩阵为：

$$S=\begin{bmatrix} a_{1}\\ a_{2}\\ b_{1}\\ b_{2}\\ c_{1}\\ c_{2}\\ 1^{2}\\ 1\\ w^{1}\\ 2^{1}\\ 1 \end{bmatrix} =\begin{bmatrix} 1\\ 3\\ 1\\ 3\\ 1\\ 3\\ 1\\ 1\\ w\\ 2\\ 1 \end{bmatrix}$$

转移矩阵为：

$$A=\begin{bmatrix} 0&1&0&0&0&0&0&0&0&0&0\\ q&p&0&1&0&1&r&t&0&0&1\\ 0&0&0&1&0&0&0&0&0&0&0\\ 0&1&v&u&0&1&0&0&1&0&0\\ 0&0&0&0&0&1&0&0&0&0&0\\ 0&1&0&1&y&x&0&1&0&1&2\\ 0&0&0&0&0&0&1&2&0&0&1\\ 0&0&0&0&0&0&0&1&0&0&1\\ 0&0&0&0&0&0&0&0&w&0&0\\ 0&0&0&0&0&0&0&0&0&z&0\\ 0&0&0&0&0&0&0&0&0&0&1 \end{bmatrix}$$

则最终的答案矩阵为：

$$T=A^{n-2}\times S$$

答案的位置显然。

总的来说算是一道套路的矩阵加速题，可以给新手做一下。不过我草稿纸写z抄代码上去成了2也是nt行为。

代码：

#include <bits/stdc++.h>

using namespace std;

template < typename Type >
void read( Type& a )
{
	a = 0;
	char ch = getchar( );
	bool minus = 0;
	while( !isdigit( ch ) )
	{
		if( ch == '-' ) minus = 1;
		ch = getchar( );
	}
	while( isdigit( ch ) )
	{
		a = ( a << 3 ) + ( a << 1 ) + ( ch ^ '0' );
		ch = getchar( );
	}
	if( minus == 1 ) a = -a;
}

template < typename Type, typename... Args >
void read( Type& t, Args&... args )
{
	read(t), read(args...);
}

void write( __int128 x )
{
	if( x < 0 )	putchar( '-' ), x = -x;
	if( x > 9 )	write( x / 10 );
	putchar( x % 10 + '0' );
}

const __int128 Maxn = 11;
__int128 n, m, p, q, r, t, u, v, w, x, y, z;
struct Matrix
{
	__int128 mat[ Maxn ][ Maxn ];
	Matrix( __int128 x = 0 ) { memset ( mat, x, sizeof ( mat ) ); }

	Matrix operator * ( const Matrix& rhs ) const
	{
		Matrix ret;
		for( __int128 i = 0; i < Maxn; ++ i )
			for( __int128 j = 0; j < Maxn; ++ j )
				for( __int128 k = 0; k < Maxn; ++ k )
					ret.mat[ i ][ j ] = ( ret.mat[ i ][ j ] + 1ll * mat[ i ][ k ] * rhs.mat[ k ][ j ] ) % m;
		return ret;
	}
} unit, meta;

void Make_Unit( )
{
	for ( __int128 i = 0; i < Maxn; ++ i )
		unit.mat[ i ][ i ] = 1;
}

void Make_Meta( )
{
	__int128 cpy[ Maxn ][ Maxn ] = 
	{
		{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ q, p, 0, 1, 0, 1, r, t, 0, 0, 1 },
		{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 1, v, u, 0, 1, 0, 0, 1, 0, 0 },
		{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
		{ 0, 1, 0, 1, y, x, 0, 1, 0, 1, 2 },
		{ 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 1 },
		{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, w, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, z, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }
	};
	memcpy( meta.mat, cpy, sizeof( cpy ) );
}

signed main( )
{
	read( n, m, p, q, r, t, u, v, w, x, y, z );
	Make_Unit( ), Make_Meta( );

	__int128 tS[ Maxn ][ Maxn ] = 
	{
		{ 1 }, { 3 }, { 1 }, { 3 }, { 1 }, { 3 }, { 1 }, { 1 }, { w }, { z }, { 1 }
	};
	Matrix S;
	memcpy( S.mat, tS, sizeof( tS ) );

	__int128 k = n - 2;
	Matrix ret = unit, base = meta;
	for( ; k; k >>= 1, base = base * base )
		if( k & 1 )	ret = ret * base;
	ret = ret * S;
	printf( "nodgd " ), write( ret.mat[ 1 ][ 0 ] ), putchar( '\n' );
	printf( "Ciocio " ), write( ret.mat[ 3 ][ 0 ] ), putchar( '\n' );
	printf( "Nicole " ), write( ret.mat[ 5 ][ 0 ] ), putchar( '\n' );
	return 0;
}