http://blog.csdn.net/lixuanjing2016/article/details/77528440

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

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

#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 {
    ll read()
    {
        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()
{
    k = fast_IO::read(), n = fast_IO::read(); ans.num[1][1] = 1;
    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;
}

矩阵乘法

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

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

readln(k,n);

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.

题解

水爆了
编译成功

测试数据 #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
readln(k);
readln(n);
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.

测试数据 #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 //主程序
readln(k);readln(n);
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.

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

readln(k,n);

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.

矩阵乘法。

矩阵乘法是正解……

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

程序40行

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

var

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

k,n,i,j:longint;

begin

readln(k);

readln(n);

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.

递归可以吗？

做的我都快把键盘吃了

几点注意:

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

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

3.用__int64

我想杀了"杜杜我爱你"

var

n,k,i,j:longint;

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

begin

readln(k);

readln(n);

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.

这个过两个点

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

Matrix67 大牛 orz。

编译通过...

├ 测试数据 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

read(k,n);

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

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

还有支持矩阵以及Matrix 67

orz…………………………

敌法闪烁就是厉害.

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

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

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