Educational Codeforces Round 60 (Rated for Div. 2) - D
链接
http://codeforces.com/contest/1117/problem/D
题意
你有两个数字：1和m，
你需要构造一个和为n的序列，问你能构造出多少种序列。答案对$10^9+7$取模。
范围
$N\le10^{18}$
$M\le100$
题解
ans(n,m) = ans(n-1,m) + ans(n-m,m)
由于m一样，所以dp[n] = dp[n-1] + dp[n-m]
矩阵快速幂
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
92
93
94
95
96
97
98
99
100
101
102
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll lenth=200;
ll mod=1e9+7;
struct Sarray{
ll data[200][200];
Sarray operator *(const Sarray&a){
Sarray tem;
for(ll i=0;i<lenth;i++){
for(ll j=0;j<lenth;j++){
for(ll k=0;k<lenth;k++){
tem.data[i][j]=(tem.data[i][j]+data[i][k]*a.data[k][j])%mod;
}
}
}
return tem;
}
Sarray operator +(const Sarray&a){
Sarray tem;
for(ll i=0;i<lenth;i++){
for(ll j=0;j<lenth;j++){
tem.data[i][j]=(data[i][j]+a.data[i][j])%mod;
}
}
return tem;
}
Sarray(const Sarray&a){
for(ll i=0;i<lenth;i++){
for(ll j=0;j<lenth;j++){
data[i][j]=a.data[i][j];
}
}
}
Sarray(){
memset(data,0,sizeof(data));
}
};
Sarray E;
void ini(){
for(ll i=0;i<lenth;i++)
for(ll j=0;j<lenth;j++)
if(i==j)E.data[i][j]=1;
else E.data[i][j]=0;
}
Sarray qpow(Sarray a,ll b){
Sarray tem=E;
while(b){
if(b&1)tem=a*tem;
a=a*a;
b>>=1;
}
return tem;
}
Sarray sigma(Sarray&p,ll n){
if(n==0)return E;
if(n==1)return E+p;
if(n&1) return (E+qpow(p,n/2+1))*sigma(p,n>>1);
else return (E+qpow(p,n/2+1))*sigma(p,n/2-1)+qpow(p,n>>1);
}
int main(){
ini();
ll n,m;
cin>>n>>m;
lenth=m;
Sarray p,r;
p.data[0][0]=1;
p.data[0][m-1]=1;
for(ll i=1;i<m;i++){
p.data[i][i-1]=1;
}
r.data[0][0]=2;
for(ll i=1;i<m;i++){
r.data[i][0]=1;
}
if(n>=m){
Sarray l=qpow(p,n-m)*r;
cout<<l.data[0][0]<<endl;
}
else{
cout<<1<<endl;
}
}
|
