第一次做就AC了，真是没话可说了

没见过矩阵乘法的可以看这个来自Flymouse网站的讲稿。

http://218.92.164.86/chenl/upload/离散数学在信息学竞赛中的运用.ppt

想都不用想……7777777^2明显超出longint

矩阵乘法~~~~~

第一次没交过，没看见hint......

So没意思……我能一次AC的题目不多的说

看看 黑客帝国 吧...

怀念玩*魔兽*的那段日子。默默地打掉了这道题。其实就是斐波拉契数列的进阶版。
没什么说的，注意**long long**
魔兽https://baike.baidu.com/item/%E9%AD%94%E5%85%BD%E4%BA%89%E9%9C%B8/128844?fr=aladdin
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const long long mod=7777777ll;
int x,y;
int f[20];
int n,m,k;
struct ju
{
long long map[105][105];
}base,now,js;
ju operator *(ju a,ju b)
{
ju c;
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
{
c.map[i][j]=0;
for(int l=0;l<k;l++)
c.map[i][j]=(c.map[i][j]+a.map[i][l]*b.map[l][j])%mod;
}
return c;
}
ju operator +(ju a,ju b)
{
ju c;
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
c.map[i][j]=(a.map[i][j]+b.map[i][j])%mod;
return c;
}
ju qmi(int b)
{
ju bb=base;
ju aa=now;
while(b)
{
if(b%2==1)
aa=aa*bb;
bb=bb*bb;
b>>=1;
}
return aa;
}
int main()
{
scanf("%d %d",&k,&n);
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
{
if(j==0) base.map[i][j]=1ll;
else if(i+1==j) base.map[i][j]=1ll;
else base.map[i][j]=0ll;
}
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
{
if(i==j) now.map[i][j]=1ll;
else now.map[i][j]=0ll;
}
f[0]=1;
for(int i=1;i<=k;i++)
for(int j=1;j<=min(i,k);j++)
f[i]+=f[i-j];
if(n<=k)
{
cout<<f[n];
return 0;
}
for(int i=1;i<=k;i++)
js.map[0][i-1]=f[k-i+1]*1ll;
js=js*qmi(n-k);
cout<<js.map[0][0];
return 0;
}

矩阵乘法
结果错在了f[i] = f[i - k] + ... + f[i - 1]没考虑i-k小于0的情况......
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define rep(i, x, y) for (long long i = x; i <= y; ++i)
#define MOD (7777777)
using namespace std;

long long b[16][16], a[16][16], c[16][16], f[16];

void run(long long p) {
if (p == 1) {
memcpy(a, b, sizeof (a));
return;
}
if (p % 2 == 0) {
run(p / 2);
memset(c, 0, sizeof (c));
rep(i, 1, 10) rep(k, 1, 10) rep(j, 1, 10) {
c[i][j] += a[i][k] * a[k][j];
c[i][j] %= MOD;
}
}
else {
run(p - 1);
memset(c, 0, sizeof (c));
rep(i, 1, 10) rep(k, 1, 10) rep(j, 1, 10) {
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= MOD;
}
}
memcpy(a, c, sizeof (a));
}
int main(int argc, const char *argv[]) {
long long k, n;
scanf("%lld%lld", &k, &n);
f[0] = 1;
rep(i, 1, 12) {
rep(j, i - k, i - 1) {
if (j < 0) continue;
f[i] += f[j];
f[i] %= MOD;
}
}
if (n <= 12) {printf("%lld\n", f[n]); return 0;}
rep(i, 1, k) b[1][i] = 1;
rep(i, 1, 10) b[i + 1][i] = 1;
run(n - 12);
long long ans = 0;
rep(i, 1, 12) {
ans += a[1][i] * f[13 - i];
ans %= MOD;
}
printf("%lld\n", ans);
return 0;
}

明显的矩阵乘法
数组要用long long
#include<cstdio>
long long f[11],g[11],s[11][11],t[11][11];int n,m;
int main()
{
scanf("%d%d",&n,&m);
if(m<=n)
{
f[0]=1;
for(int i=1;i<=m;++i)
for(int j=1;j<=i;++j)
f[i]+=f[i-j];
printf("%lld\n",f[m]);
return 0;
}
m-=n;f[0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
f[i]+=f[i-j];
for(int i=1;i<n;++i)
s[i+1][i]=s[i][n]=1;
s[n][n]=1;
for(;m;m>>=1)
{
if(m&1)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
g[i]=(g[i]+f[j]*s[j][i])%7777777;
for(int i=1;i<=n;++i)
f[i]=g[i],g[i]=0;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
long long &temp=t[i][j];
for(int k=1;k<=n;++k)
temp=(temp+s[i][k]*s[k][j])%7777777;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
s[i][j]=t[i][j],t[i][j]=0;
}
printf("%lld\n",f[n]);
return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 25;
const int MOD = 7777777;
typedef long long LL;
int t,m,n,k;
struct Mat
{
LL s[12][12];
}a,b;
Mat multiply(Mat x, Mat y)
{
Mat c;
memset(c.s,0,sizeof(c.s));
for(int i = 0;i < k; ++i)
{
for(int j = 0;j < k; ++j)
{
for(int z = 0; z < k; ++z)
{
c.s[i][j] += x.s[i][z] * y.s[z][j];
c.s[i][j] %= MOD;
}
}
}
return c;
}
void init()
{
memset(a.s,0,sizeof(a.s));
memset(b.s,0,sizeof(b.s));
a.s[0][0] = 1;
for(int i = 1; i < k; ++i)
{
a.s[i][i-1] = 1;
a.s[0][i] = 1;
}
for(int i = 0; i < k;i++)
b.s[i][0] = 1;
}
LL calc()
{
while(n)
{
if(n & 1)
b = multiply(b,a);
a = multiply(a,a);
n >>= 1;
}
return b.s[0][0];
}
int main()
{
#ifdef CDZSC_OFFLINE
freopen("in.txt","r",stdin);
#endif //CDZSC_OFFLINE
while(~scanf("%d%d",&k,&n))
{
init();
LL ans = calc();
printf("%lld\n",ans);
}
}

有什么问题就去找黎明前的光

#include<cstdio>
#include<cstring>
#define MAXN 15
using namespace std;

int n, k;

struct Matrix{
long long int m[MAXN][MAXN];

}s, t;

void init(){
int sum = 1;
for(int i=1; i<=k; i++){
s.m[i][i+1] = 1;
s.m[k][i] = 1;
t.m[i][1] = sum;
sum += t.m[i][1];
}
}

void clear(Matrix &x){
for(int i=1; i<=k; i++)
for(int j=1; j<=k; j++)
x.m[i][j] = 0;
}

Matrix cheng(Matrix a, Matrix b){
Matrix c;
clear(c);
for(int i=1; i<=k; i++)
for(int j=1; j<=k; j++)
for(int u=1; u<=k; u++){
c.m[i][j] += a.m[i][u] * b.m[u][j];
c.m[i][j] %= 7777777;
}
return c;
}

Matrix build(int x){
if(x == 1)
return s;
Matrix a, b;
if(x&1){
a = build(x >> 1);

b = cheng(a, a);
b = cheng(b, s);

}
else{
a = build(x >> 1);
b = cheng(a, a);
}
return b;
}

int main()
{
scanf("%d%d", &k, &n);
init();
if(n != k){
Matrix ans = cheng( build(n - k), t);
printf("%lld", ans.m[k][1]);
}
else
printf("%lld", t.m[k][1]);
return 0;
}
矩阵乘法，要注意顺序。

0ms飘过
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 284 KiB, score = 10
Accepted, time = 0 ms, mem = 284 KiB, score = 100

点击查看程序源码+详细题解

矩阵乘法～

太经典了～

水过

编译通过...├ 测试数据 01：答案正确...ms├ 测试数据 02：答案正确...ms├ 测试数据 03：答案正确...ms├ 测试数据 04：答案正确...ms├ 测试数据 05：答案正确...ms├ 测试数据 06：答案正确...ms├ 测试数据 07：答案正确...ms├ 测试数据 08：答案正确...ms├ 测试数据 09：答案正确...ms├ 测试数据 10：答案正确...msAccepted 有效得分：100 有效耗时：0ms

矩阵乘法优化递推式~~

复杂度：O(logn)