Educational Codeforces Round 60 (Rated for Div. 2) - D

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

链接

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;

//函数参数输入,返回值输出
//特别注意lenth一定要改,不然每次都遍历到最大的矩阵会tle
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;
}

//sigma(p^i) from 0 to n [0,n]
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;
}
}