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;
}