# 97 条题解

• @ 2017-08-24 12:57:01
• @ 2019-03-17 15:06:30
``````#include <iostream>
#include <cstring>
using namespace std;
const int mod = 7777777;
struct mt {
long long a[100][100], n, m;
mt(int _n, int _m) {
n = _n;
m = _m;
memset(a, 0, sizeof(a));
}
mt operator*(mt &x) {
mt t = mt(n, x.m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < x.m; j++) {
for (int k = 0; k < m; k++) {
t.a[i][j] += a[i][k] * x.a[k][j];
t.a[i][j] %= mod;
}
}
}
return t;
}
mt operator^(long long x) {
mt t = *this, res = mt(n, n);
for (int i = 0; i < n; i++) {
res.a[i][i] = 1;
}
while (x) {
if (x % 2 == 1) {
res = res * t;
}
x /= 2;
t = t * t;
}
return res;
}
};
int main() {
long long n, k;
cin >> k >> n;
mt a(k, k), b(k, 1);
for (int i = 0; i < k - 1; i++) a.a[i][i + 1] = 1;
for (int i = 0; i < k; i++) a.a[k - 1][i] = 1;
b.a[k - 1][0] = 1;
a = (a ^ (n)) * b;
cout << a.a[k - 1][0] << endl;
return 0;
}
``````
• @ 2018-12-12 00:41:28
``````#include<bits/stdc++.h>
using namespace std;
const int MOD=7777777;
int k,n;
struct node{
long long a[12][12];
}c,ans;
inline node Mul1(node x,node y){
node res;
memset(res.a,0,sizeof(res.a));
for(int i=1;i<=k;i++)
for(int j=1;j<=1;j++)
for(int l=1;l<=k;l++)
res.a[i][j]=(res.a[i][j]+x.a[i][l]*y.a[l][j])%MOD;
return res;
}
inline node Mul2(node x,node y){
node res;
memset(res.a,0,sizeof(res.a));
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
for(int l=1;l<=k;l++)
res.a[i][j]=(res.a[i][j]+x.a[i][l]*y.a[l][j])%MOD;
return res;
}
int main(){
cin>>k>>n;
ans.a[k+1][1]=1;
for(int i=1;i<=k;i++)
for(int j=0;j<i;j++) ans.a[k-i+1][1]+=ans.a[k-j+1][1];
for(int i=1;i<=k;i++) c.a[1][i]=1;
for(int i=2;i<=k;i++) c.a[i][i-1]=1;
if(n<=k) cout<<ans.a[k+1-n][1];
else{
n-=k;
while(n){
if(n&1) ans=Mul1(c,ans);
c=Mul2(c,c);
n>>=1;
}
cout<<ans.a[1][1];
}
}
``````
• @ 2019-01-05 14:17:47
``````#include <bits/stdc++.h>
#define loc(x,y) (x-1)*m+y
#define jh(x,y) x^=y^=x^=y
#define lowbit(x) (x&-x)
#define rg register
#define inl inline
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5 + 10, mod = 7777777;
using namespace std;
namespace fast_IO {
{
rg ll num = 0;
rg char ch;
rg bool flag = false;
while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
if (ch == EOF)return ch; if (ch == '-')flag = true; else num = ch ^ 48;
while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
num = (num << 1) + (num << 3) + (ch ^ 48);
if (flag)return -num; return num;
}
void write(rg long long x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
};
ll k, n;
struct Matrix {
ll num[11][11];
Matrix() { memset(num, 0, sizeof(num)); }
Matrix operator *(rg Matrix &s)
{
rg Matrix ans;
for (rg int i = 1; i <= k; ++i)
for (rg int j = 1; j <= k; ++j)
for (rg int t = 1; t <= k; ++t)
(ans.num[i][j] += num[i][t] * s.num[t][j]) %= mod;
return ans;
}
}base, ans;
inl void ksm(rg ll b)
{
rg Matrix tmp = base;
while (b)
{
if (b & 1)ans = ans * tmp;
tmp = tmp * tmp;
b >>= 1;
}
}

int main()
{
for (rg int i = 1; i <= k; ++i)base.num[1][i] = 1;
for (rg int i = 2; i <= k; ++i)base.num[i][i - 1] = 1;
ksm(n), fast_IO::write(ans.num[1][1]);
return 0;
}
``````
• @ 2018-07-28 15:53:38

矩阵乘法

``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,k;
struct martix {
int r,c;
ll a[20][20];
martix() {
r=c=0;
memset(a,0,sizeof a);
}
martix operator*(martix x) {
int r2=x.r,c2=x.c;
martix res;
res.r=r,res.c=c2;
FOR(i,res.r) FOR(j,res.c) {
FOR(k,c) {
res.a[i][j]+=(a[i][k]*x.a[k][j])%mod;
res.a[i][j]%=mod;
}
}
return res;
}
void operator=(martix x) {
r=x.r,c=x.c;
FOR(i,r) FOR(j,c) a[i][j]=x.a[i][j];
}
};
martix mpow(martix a,int b) {
martix res=a;
b--;
while (b) {
if (b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int f[20];
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin>>k>>n;
if (n==1) {
cout<<1<<endl;
return 0;
}
martix t,t2;
t.r=k,t.c=k;
FOR(i,k-1) t.a[i][i+1]=1;
FOR(i,k) t.a[k][i]=1;
t=mpow(t,n-1);
FOR(i,k) REP(j,i-k,i-1) if (j<=0) {
++f[i];
j=0;
} else f[i]+=f[j];
t2.r=k,t2.c=1;
FOR(i,k) t2.a[i][1]=f[i];
t=t*t2;
cout<<t.a[1][1]<<endl;
return 0;
}
``````
• @ 2012-08-18 21:26:51

type

matrix=array[1..10,1..10] of int64;

var

tmp,a,f:matrix;

n,k,i:longint;

procedure cheng(var a,b:matrix;p,q,r:longint);

var

i,j,k:longint;

begin

fillchar(tmp,sizeof(tmp),0);

for i:=1 to p do

for j:=1 to r do

for k:=1 to q do

tmp:=(tmp+a*b[k,j]) mod 7777777;

a:=tmp;

end;

begin

for i:=1 to k do

a:=1;

for i:=1 to k-1 do

a:=1;

f[1,1]:=1;

while n>0 do

begin

if n and 1=1 then

cheng(f,a,1,k,k);

cheng(a,a,k,k,k);

n:=n shr 1;

end;

writeln(f[1,1]);

end.

• @ 2014-08-19 09:34:19
• @ 2013-11-01 22:27:54

水爆了
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 828 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #2: Accepted, time = 7 ms, mem = 824 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 828 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 828 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 828 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 828 KiB, score = 10

Accepted, time = 7 ms, mem = 828 KiB, score = 100

代码
program p1067;
type arr=array[0..11,1..11] of int64;
var n,k:longint;
num:array[0..100] of int64;
a,b,c:arr;
//
procedure init;
begin
end;
//
procedure makeb(k:longint);
var i:longint;
begin
a[1,1]:=1;
for i:=2 to k do a[1,i]:=a[1,i-1]*2;
end;
//
procedure makea(p:longint);
var i,j,k:longint;
begin
for i:=1 to p do b[i,p]:=1;
for i:=2 to p do b[i,i-1]:=1;
end;
//
procedure cheng(a,b:arr;var c:arr);
var i,j,p:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to k do
for j:=1 to k do
for p:=1 to k do c[i,j]:=(c[i,j]+a[i,p]*b[p,j]) mod 7777777;
end;
//
procedure main;
var i:longint;
begin
makeb(k);
makea(k);
if n<=k then begin write(a[1,n]);halt;end;
dec(n,k+1);
while n<>0 do
begin
inc(num[0]);num[num[0]]:=n mod 2;n:=n shr 1;
end;
c:=b;
for i:=1 to num[0] do
begin
if num[i]=1 then cheng(c,b,c);
cheng(b,b,b);
end;
cheng(a,c,c);
end;
//
procedure print;
begin
write(c[1,k]);
end;
//
begin
init;
main;
print;
end.

• @ 2013-07-24 09:51:54

测试数据 #0: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 776 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 792 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 840 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 828 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 836 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 832 KiB, score = 10
Accepted, time = 15 ms, mem = 840 KiB, score = 100

就是构造矩阵来实现递推：
f[n]:=f[n-k]+……+f[n-1];
举个例子，假设k=2
[f[a] f[a+1]]*
|0 1|=[f[a+1] f[a+2]]
|1 1|
显然就有
[f[1] f[2]]*
|0 1|^(n-k)=[f[n-1] f[n]]
|1 1|
这样就可以求出f[n]
矩阵的n次方运算要用快速幂来解决
至于矩阵的结合律的证明可以上网上找，楼下也有说明

const x=7777777;
type matrix=array[1..10,1..10] of int64;
var f:array[0..10] of int64;
base:matrix;
i,j:longint;
ans,c,n,k:int64;
procedure build; //构造矩阵
var i:longint;
begin
fillchar(base,sizeof(base),0);
for i:=2 to k do base[i,i-1]:=1;
for i:=1 to k do base[i,k]:=1;
end;
function mul(a,b:matrix):matrix; //矩阵乘法
var i,j,m:longint;
begin
for i:=1 to k do
for j:=1 to k do begin
mul[i,j]:=0;
for m:=1 to k do
mul[i,j]:=(mul[i,j]+((a[i,m] mod x)*(b[m,j] mod x) mod x)) mod x;
end;
end;
function sq(a:matrix):matrix; //矩阵平方
begin
sq:=mul(a,a);
end;
function speedmi(b:matrix;c:int64):matrix; //矩阵快速幂
begin
if c>1 then begin
if not odd(c) then begin //如果c为偶数，则b^c:=(b^2)^(c/2)
speedmi:=speedmi(sq(b),c shr 1);
end
else begin //如果c为奇数，则b^c:=(b^2)^(c div 2)*b
speedmi:=mul(speedmi(sq(b),c shr 1),b);
end;
end;
if c=1 then speedmi:=b;
end;
begin //主程序
fillchar(f,sizeof(f),0);
f[1]:=1;
for i:=2 to k do begin
f[i]:=1;
for j:=1 to i-1 do
f[i]:=f[i]+f[j];
end;
if n<=k then begin write(f[n]);exit;end;
build;
c:=n-k;
base:=speedmi(base,c);
ans:=0;
for i:=1 to k do
ans:=(ans+(f[i] mod x)*(base[i,k] mod x)) mod x;
write(ans);
end.

• @ 2010-07-08 11:00:26

type

matrix=array[1..10,1..10] of int64;

var

tmp,a,f:matrix;

n,k,i:longint;

procedure cheng(var a,b:matrix;p,q,r:longint);

var

i,j,k:longint;

begin

fillchar(tmp,sizeof(tmp),0);

for i:=1 to p do

for j:=1 to r do

for k:=1 to q do

tmp:=(tmp+a*b[k,j]) mod 7777777;

a:=tmp;

end;

begin

for i:=1 to k do

a:=1;

for i:=1 to k-1 do

a:=1;

f[1,1]:=1;

while n>0 do

begin

if n and 1=1 then

cheng(f,a,1,k,k);

cheng(a,a,k,k,k);

n:=n shr 1;

end;

writeln(f[1,1]);

end.

矩阵乘法。

• @ 2009-10-31 19:29:34

矩阵乘法是正解……

学了这道题可以充分体会到矩阵乘法在1d/1d问题上优化的威力，

程序40行

另外，请注意边界情况，我看到贴程序的某几君都没有处理好。

• @ 2009-10-25 19:27:46

var

f:array[0..12] of longint;

k,n,i,j:longint;

begin

fillchar(f,sizeof(f),0);

f[0]:=1;

for i:=1 to k do

for j:=0 to i-1 do

f[i]:=f[i]+f[j];

for i:=k+1 to n do

begin

for j:=1 to k do

f[k+1]:=(f[k+1]+f[j]) mod 7777777;

for j:=1 to k+1 do

f[j]:=f[j+1];

end;

write(f[k]);

end.

递归可以吗？

• @ 2009-10-19 17:48:32

做的我都快把键盘吃了

几点注意:

1. 构造矩阵(都不知道那些牛 杂么想到的)

2.用 "重复平方法" 求矩阵快素幂

3.用__int64

我想杀了"杜杜我爱你"

• @ 2009-10-12 13:29:34

var

n,k,i,j:longint;

a:array[-20..100000] of int64;

begin

fillchar(a,sizeof(a),0);

a[0]:=1;

for i:=1 to n do begin

for j:=1 to k do

a[i]:=a[i]+a;

end;

writeln(a[n] mod 7777777);

end.

这个过两个点

• @ 2009-09-27 21:10:48

思路跟 zsy90943（下面四楼） 一样 ——矩阵乘法。

Matrix67 大牛 orz。

• @ 2009-09-25 21:56:07

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|---|---|---|---|---|---|

program p1067;

const

m=7777777;

type

matrix=array[1..20,1..20] of int64;

var

base,juzhen,tp:matrix;

f:array[1..20] of int64;

k,i,j,n,t:longint;

s:int64;

procedure chen(var a,b:matrix);

var

i,j,t:integer;

s:int64;

begin

fillchar(tp,sizeof(tp),0);

for i:=1 to k do

for j:=1 to k do

begin

s:=0;

for t:=1 to k do s:=(s+(a mod m)*(b[t,j] mod m)) mod m;

tp:=s

end;

b:=tp;

end;

procedure kuaisu(base:matrix; n:longint);

begin

if n=1 then begin juzhen:=base; exit; end;

kuaisu(base,n div 2);

chen(juzhen,juzhen);

if n mod 2=1 then chen(base,juzhen);

end;

procedure init;

var

i,j:integer;

begin

fillchar(base,sizeof(base),0);

for j:=1 to k-1 do base[j+1,j]:=1;

for i:=1 to k do base:=1;

end;

begin

if k=1 then begin write(1); halt; end;

fillchar(f,sizeof(f),0);

f[1]:=1;

for i:=2 to k do

begin

f[i]:=1;

for j:=1 to i-1 do f[i]:=f[i]+f[j];

end;

if n

• @ 2009-09-24 07:19:25

支持魔兽，支持精灵，支持守望，支持闪烁……

还有支持矩阵以及Matrix 67

orz…………………………

• @ 2009-09-18 01:22:14

敌法闪烁就是厉害.

• @ 2009-09-09 20:57:58

我喜欢不死 (*^__^*) 嘻嘻

人族大法的群传不更好吗？？

• @ 2009-09-07 19:56:30

WARDEN确实是个弱智，放几个毒就没蓝了，还是DH好啊。

ID
1067

6

(无)

2887

784

27%

11