【Vijos1067】守望者的烦恼

来源和评测点

杜杜我爱你
Vijos1067
Caioj1485

题目

【题目大意】
有n个格子,从入口出发(注意,入口不是第一个格子,要另外计算),
需要走到最后一个格子(即出口,第n个格子)。
每走一步可选择走过1~k个格子,求能走到出口的方案数。
【输入格式】
仅一行,含有两个整数k(1<=k<=10),n(1<=n<=2^31-1)
【输出格式】
输出方案数mod 7777777的值
【输入样例】
2 4
【输出样例】
5

分析

首先想DP,f[i]=sigma(p=i-k~i-1)[f[p]]
然后因为n太大,考虑加速
列向量(k+1)/*1,表示近几个f的值,然后推导出一个操作矩阵表示把列向量往前推并计算出最后一个值,
然后把这个操作矩阵快速幂n-k-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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=20;
//*******************全局定义*******************
typedef long long ll;
struct matrix
{
int row,col;
ll p[MAXN][MAXN];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************全局变量*******************
ll mod=7777777;
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c.p[i][j]=(c.p[i][j]%mod+a.p[i][k]*b.p[k][j]%mod)%mod;
c.row=n;c.col=p;
return c;
}
matrix pre(int fn)
{
matrix c;c.row=c.col=fn;
for(int i=1;i<=fn;i++) c.p[i][i]=1;
return c;
}
matrix power(matrix a,int e)
{
matrix c=pre(a.row);
while(e>0)
{
if(e%2==1) --e,c=cheng(c,a);//a*c也行
a=cheng(a,a);e/=2;
}
return c;
}
//*******************主函数*******************
int main()
{
int k,n;scanf("%d%d",&k,&n);
matrix f;f.row=k+1;f.col=k+1;
for(int i=1;i<=k;i++) f.p[i][i+1]=1;
for(int i=2;i<=k+1;i++) f.p[k+1][i]=1;
matrix ans;ans.row=k+1;ans.col=1;
for(int i=1;i<=k+1;i++)
{
if(i<=k) ans.p[i][1]=1;//一步跳过来
for(int j=1;j<=i-1;j++) ans.p[i][1]=(ans.p[i][1]+ans.p[j][1])%mod;
}
if(n<=k)//debug
{
printf("%lld",ans.p[n][1]);
return 0;
}
ans=cheng(power(f,n-k-1),ans);
printf("%lld",ans.p[k+1][1]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/守望者的烦恼.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%