专栏文章

题解：SP2450 RABBIT1 - Counting Rabbits

HHhy140516
SP2450题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioovzt4
此快照首次捕获于
2025/12/02 22:44
3 个月前
此快照最后确认于
2025/12/02 22:44
3 个月前
查看原文

题意

求斐波那契数列的第 nn 项模上 2m2 ^ m 的值。

分析

前置知识：矩阵加速。
矩阵的三种功能：
  1. 解方程（省选）。
  2. 加速线性 DP（S组）。
  3. 加速 floyd（S组）。
性质：
1.常数乘法：假设
A=[1234]，A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}，
则
k∗A=[1∗k2∗k3∗k4∗k]。k*A = \begin{bmatrix} 1*k & 2*k \\ 3*k & 4*k \end{bmatrix}。
2.矩阵乘法
A=[abcd]，B=[xyzwub]，A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}，\\ B = \begin{bmatrix} x & y & z \\ w & u & b \end{bmatrix}，
则
A×B=[ax+bway+buaz+bvcx+dwcy+ducz+dv]。A \times B = \begin{bmatrix} ax + bw & ay + bu & az + bv \\ cx + dw & cy + du & cz + dv \end{bmatrix}。
AA 矩阵的第一行乘 BB 矩阵的第 jj 列等于 CC 矩阵的第 ii 行第 jj 列。
假如 AA 是 nn 行 mm 列，BB 是 mm 行 kk 列，则 CC 是 nn 行 kk 列。
[1234]×[1001]=[1234]。[10⋯001⋯0⋮⋮⋱⋮00⋯1]\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \times \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}。 \\ \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}
就是单位矩阵。
普通的斐波那契数列 Fi=Fi−1+Fi−2F_i = F_{i - 1} + F_{i - 2}，可以通过矩阵乘法求出FnF_n。
可以发现，每次 Fi=Fi−1+Fi−2F_i = F_{i - 1} + F_{i - 2}，Fi−1=Fi−1F_{i - 1} = F_{i - 1}，通过矩阵乘法能做到这样的操作，每次乘的矩阵是
[0111]。\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}。
而要乘 n−2n - 2 次，自然想到优化是快速幂，就是
[F1F2]×[0111]n−2=[Fn−1Fn]。\begin{bmatrix} F_1 & F_2 \end{bmatrix} \times { \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} } ^ {n - 2} = \begin{bmatrix} F_{n - 1} & F_n \end{bmatrix}。
结合律
A×B×C=(A×B)×C=A×(B×C)，A \times B \times C = (A \times B) \times C = A \times (B \times C)，
但
A×B≠B×A。A \times B \ne B \times A。

代码

CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
	cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
	string s=#__VA_ARGS__,s2="";\
	vector<string>v;\
	for(auto i:s){\
		if(i==','){\
			v.push_back(s2);\
			s2="";\
		}else{\
			s2+=i;\
		}\
	}\
	v.push_back(s2);\
	vector<int>v2={__VA_ARGS__};\
	for(int i=0;i<v.size()-1;i++){\
		cout<<v[i]<<"="<<v2[i]<<"\n";\
	}\
	cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 105 , MOD = 1e9 + 7 , INF = 1e9 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
int n , mod ; 
struct node
{
  int n , m , a[kMaxN][kMaxN] ;
  node(int x , int y) 
  {
  	n = x ;
  	m = y ;
  	memset(a , 0 , sizeof a) ;
	}
	node operator * (const node b)
	{
		node c(n , b.m) ;
		for( int i = 1 ; i <= n ; i++ )
		{
			for( int j = 1 ; j <= b.m ; j++ )
			{
				for( int k = 1 ; k <= m ; k++ )
				{
					c.a[i][j] += a[i][k] * b.a[k][j] ;
					c.a[i][j] %= mod ;
				}
			}
		}
		return c ;
	}
};
node ksm(node a , int b)
{
	node mul(2 , 2) ;
	for( int i = 1 ; i <= 2 ; i++ ) mul.a[i][i] = 1 ;
	while(b)
	{
		if(b & 1) mul = mul * a ;
		a = a * a ;
		b >>= 1 ;
	}
	return mul ;
}
inline int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1 ;
        ch = getchar() ;
    }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
    return x * f ;
}
void write(int x)
{
    if(x < 0) putchar('-') , x = -x ;
    if(x > 9) write(x / 10) ;
    putchar(x % 10 + '0') ;
}
void init()
{
  
}
void work()
{
  init() ;
  int m ;
  cin >> n >> m ;
  mod = 1 << m ;
  if(n <= 2) {cout << 1 % mod << "\n" ; return ;}
  node a(2 , 2) , b(1 , 2) ;
  a.a[2][1] = 1 ;
  a.a[1][2] = 1 ;				
	a.a[1][1] = 1 ;
	a = ksm(a , n - 1) ;	
	b.a[1][1] = 1 ;
	b.a[1][2] = 1 ;
	b = b * a ;
	cout << b.a[1][1] << "\n" ;
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
  ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  cin >> t ;
  while(t--) work() ;
  return 0 ;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...