【CSU-2138】解题报告（数学，矩阵快速幂）

原始题目

2138: Rikka's Set

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 44
  • Solved: 11

Description

Rikka is poor at math. Now she asks you for help.

A set is known as extraordinary set when the minimum integer of it is equal to its size. min{x : x ∈ S}=|S| For example, S = {3, 7, 8} is extraordinary.

gn is the number of extraodinary subsets of {1, 2, ..., n}.

Rikka wants to know the value of gn.

Input

Input consists of one integer n(1 ≤ n ≤ 1018) ### Output Output a single integer gnmod1000000009 ### Sample Input 16 ### Sample Output 987 ### Hint ### Source ### Author xm

题目大意

给定一个{1,2,3......n}的集合，问有多少个集合中元素个数等于集合中元素最小值的子集。 # 解题思路 - 对于给定的n， - n=1，易知为1 - n=2，易知为1 - n>=3，我们很容易根据题目想到答案的表达式 Mathjax显示不出来好吧。。。就是 C(n-i,i-1) i从2到n的求和+1。

  • 列出前几项，我们发现实际为斐波那契数列（等价证明还没想明白）
  • 运用矩阵快速幂可得到答案。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <queue>
#define mod 1000000009  //这里定义模 
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
struct Matrix
{
	ll a[2][2];
	Matrix()
	{
		memset(a,0,sizeof(a));
	}
	Matrix operator * (const Matrix y) 
	{  
        Matrix ans;  
        for(int i = 0; i < 2; i++)  
            for(int j = 0; j < 2; j++)    
                for(int k = 0; k < 2; k++)    
                    ans.a[i][j] += (a[i][k]*y.a[k][j])%mod;    
        return ans;  
    }
	Matrix operator = (const Matrix y)
	{
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				a[i][j]=y.a[i][j];
	}
	Matrix operator *= (const Matrix y)
	{
		Matrix ans;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					ans.a[i][j] += (a[i][k]*y.a[k][j])%mod;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				a[i][j]=ans.a[i][j];
	}
}; 

Matrix qpow(ll x)
{
	Matrix ans;
	ans.a[0][0]=ans.a[1][1]=1; //单位矩阵 
	Matrix mul;
	mul.a[0][0]=mul.a[0][1]=mul.a[1][0]=1;
	while(x)
	{
		if(x&1)
			ans *= mul;
		mul*=mul;
		x>>=1; 
	} 
	return ans;
}
ll pow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a%mod);
		a=a*a%mod;
		b>>=1;
	}
	return ans;
	
}
ll n;
int main()
{	
	while(~scanf("%lld",&n))
	{
		if(n==1)
			printf("1\n");
		else if(n==2) printf("1\n");
		else if(n==3) printf("2\n");
		else if(n==4) printf("3\n");
		else if(n==5) printf("5\n");
		else
		{
			Matrix m=qpow(n-2);
			printf("%lld\n",(m.a[0][0]+m.a[0][1])%mod); 
		} 
		
	}
}

收获与反思

  • 多尝试一下前几项，发现规律
  • 矩阵快速幂练习