hdu 4602 Partition

本文从WordPress迁移而来, 查看全部WordPress迁移文章

数学推公式 or 矩阵快速幂

【2013多校联合训练第一场】

题意：比较易懂的题意，给出一个n，可以由多种方式分解它

1
2
3
4
5
6
7
8
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=1+3
4=2+2
4=3+1
4=4

然后给定一个数字m，问在这里分解中m这个数字出现了几次

多校的第一场，看到这题，觉得答案肯定很大，没想法，但是觉得这么的数据，肯定是数学题，第一反应是，找规律，所以写了一个dfs的暴力程序，把1<=n<=20，对于每个n的每个因子出现了几次都打印出来，然后发现了规律

下面给出n<=10的时候打出来的表

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
n = 1
1[1]
n = 2
1[2]
2[1]
n = 3
1[5]
2[2]
3[1]
n = 4
1[12]
2[5]
3[2]
4[1]
n = 5
1[28]
2[12]
3[5]
4[2]
5[1]
n = 6
1[64]
2[28]
3[12]
4[5]
5[2]
6[1]
n = 7
1[144]
2[64]
3[28]
4[12]
5[5]
6[2]
7[1]
n = 8
1[320]
2[144]
3[64]
4[28]
5[12]
6[5]
7[2]
8[1]
n = 9
1[704]
2[320]
3[144]
4[64]
5[28]
6[12]
7[5]
8[2]
9[1]
n = 10
1[1536]
2[704]
3[320]
4[144]
5[64]
6[28]
7[12]
8[5]
9[2]
10[1]

很明显看到是一个数列，但是这个数列有什么规律呢？我们这样定义项数，对于n，因子x=n为第1项，x=n-1为第2项………….x=1为第n项

第1，2，3项是分别是1,2,5，我们从第4项看看会怎样

1
2
3
4
f[4] = 12 = 5 + 2*2 + 3
f[5] = 28 = 12 + 2*5 + 6
f[6] = 64 = 28 + 2*12 + 12
f[7] = 144 = 64 + 2*28 + 24

规律就很明显了，f[n] = f[n-1] + 2 f[n-2] + 3 2^(n-4);

这种递推式子，如果就这样推上去，复杂度是O(n)，但是留意到这题数据很大为10^9，所以不能线性推，那么就构造矩阵吧

对于矩阵[ f[n-1] , f[n-2] , 3*2^(n-4) ] ，我们构造一个矩阵[ A ]，两者进行一次矩阵乘法后能得到

[ f[n] , f[n-1] , 3*2^(n-3) ]

[ A ]还是很容易想的，就是

1
2
3
|  1  1  0  |
|  2  0  0  |
|  1  0  2  |

那么要推出后面m项，就乘上m个[ A ]即可，而m个[A]相乘，就可以利用矩阵快速幂

一开始由[ f[3] , f[2] , 3] = [ 5 , 2 , 3]，要推第k项的话

就是[ 5 , 2 , 3] [A]^(k-3) = [f[k] , f[k-1] , 32^(k-3)]，我们只取出f[k]即可

至于矩阵快速幂怎么写这里就不说了，道理就是二分

比赛的时候写的是迭代版的，回来后把递归版的也写了

不过赛后同学说不用这么麻烦，因为公式还没有推彻底，推彻底后，就一个公式可以了

不过也好，当做练习了一下矩阵快速幂和构造矩阵

!!!!!!!!!!!!!!!!注意一个大水坑，对于一个数字n，查询x出现了几次，这个x可能打过n，答案就是0，就是被这大水坑搞了4次wa!!!!!!!

迭代版

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
/*
1 1 0
2 0 0
1 0 2
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 3010
#define ll long long
#define MOD 1000000007
const ll mat[3][3] = {1,1,0,2,0,0,1,0,2};
const ll _mat[3][3] = {1,0,0,0,1,0,0,0,1};

ll f[3],fn[3];
ll a[N][3],b[3][3],x[3][3];

void solve(int k){
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++){
			a[i][j] = mat[i][j];
			b[i][j] = _mat[i][j];
		}
	while(k){
    if(k % 2){
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				x[i][j] = (b[i][0]*a[0][j] + b[i][1]*a[1][j] + b[i][2]*a[2][j]) % MOD;
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				b[i][j] = x[i][j];
        }
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                x[i][j] = (a[i][0]*a[0][j] + a[i][1]*a[1][j] + a[i][2]*a[2][j]) % MOD;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                a[i][j] = x[i][j];
        k /= 2;
    }
    fn[0] = (f[0]*b[0][0] + f[1]*b[1][0] + f[2]*b[2][0]) % MOD;
    cout << fn[0] << endl;
}

int main(){
    int cas;
    int n,m;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&m);
        if(m > n){ puts("0"); continue;} //大水坑
        int index = n - m + 1;
        if(index == 1){ puts("1"); continue;}
        else if(index == 2) {puts("2"); continue;}
        else if(index == 3) {puts("5"); continue;}
        f[0] = 5; f[1] = 2; f[2] = 3;
        int cnt = index - 3;
        solve(cnt);
    }
    return 0;
}

递归版

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
/*
1 1 0
2 0 0
1 0 2
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 3010
#define ll long long
#define MOD 1000000007
const int mat[3][3] = {1,1,0,2,0,0,1,0,2};

ll f[3],fn[3];
ll a[N][3],b[3][3];

void Pow(int r,int m){
	if(m == 1){
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				a[r+i][j] = mat[i][j];
		return ;
	}
	Pow(r+3 , m/2);
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			a[r+i][j] = (a[r+3+i][0]*a[r+3][j] + a[r+3+i][1]*a[r+4][j] + 
                                    a[r+3+i][2]*a[r+5][j]) % MOD;
	if(m&1){
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				b[i][j] = (a[r+i][0]*mat[0][j] + a[r+i][1]*mat[1][j] + a[r+i][2]*mat[2][j]) % MOD;
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				a[r+i][j] = b[i][j];
	}
}

void solve(ll m){
    Pow(0,m);
    ll fn[3];
    fn[0] = (f[0]*a[0][0] + f[1]*a[1][0] + f[2]*a[2][0]) % MOD;
    cout << fn[0] << endl;
}

int main(){
    int cas;
    int n,m;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&m);
        if(m > n){ puts("0"); continue;} //大水坑
        int index = n - m + 1;
        if(index == 1){ puts("1"); continue;}
        else if(index == 2) {puts("2"); continue;}
        else if(index == 3) {puts("5"); continue;}
        f[0] = 5; f[1] = 2; f[2] = 3;
        int cnt = index - 3;
        solve(cnt);
    }
    return 0;
}