97 条题解

  • 3
    @ 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;
    }
    
  • 3
    @ 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];
        }
    }
    
  • 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 {
        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;
    }
    
  • 1
    @ 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;
    }
    
  • 1
    @ 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

    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
    @ 2014-08-19 09:34:19
  • 0
    @ 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
    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
    @ 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 //主程序
    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.

  • 0
    @ 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

    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
    @ 2009-10-31 19:29:34

    矩阵乘法是正解……

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

    程序40行

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

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

    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.

    递归可以吗?

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

    做的我都快把键盘吃了

    几点注意:

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

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

    3.用__int64

    我想杀了"杜杜我爱你"

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

    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.

    这个过两个点

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

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

    Matrix67 大牛 orz。

  • 0
    @ 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

    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

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

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

    还有支持矩阵以及Matrix 67

    orz…………………………

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

    敌法闪烁就是厉害.

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

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

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

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

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

信息

ID
1067
难度
6
分类
动态规划 | 线性代数 | 矩阵乘法 点击显示
标签
(无)
递交数
2887
已通过
784
通过率
27%
被复制
11
上传者