12 条题解

  • 1
    @ 2016-10-31 21:27:36
    这题线性递推,需要用矩阵乘法。
    构建矩阵:由于有一个常数,表示结果的矩阵需要1*2,可设A0=【x0,c】,An=【xn,c】
    然后 An=【xn,c】=A0* (B^n) 由于Am(1*2)*B(2*2)=An(1*2) (n=m+1,m>=0)
    所以B是个2*2的矩阵,
    设B=
    [b11,b12]
    [b21,b22]
    则 An(1,1)=Am(1,*)*B(*,1)=x*a+c=x*b11+c*b21
    An(1,2)=Am(1,*)*B(*,2)=c=x*b12+c*b22
    可知b11=a,b21=1,b12=0,b22=1
    所以B=
    [a,0]
    [1,1]
    然后套用矩阵乘模板求出An=A0*(B^n)即可
    乘的时候要用取模的“快速”乘防止溢出。
    
    Accepted, time = 0 ms, mem = 528 KiB, score = 100
    代码:
    #include<stdio.h>
    typedef long long ll; 
    #define GetI64(x) scanf("%I64d",&x)
    #define PutI64(x,arg...) printf("%I64d" arg,x)
    
    ll mod;
    
    ll mul(ll a,ll b){
        ll ans=0;
        while(b){
            if(b&1)ans=(ans+a)%mod;
            a=(a+a)%mod;
            b>>=1;
        }
        return ans;
    }
    
    
    
    struct mat{
        int m,n;
        ll a[3][3];
        mat(int M=0,int N=0){m=M;n=N;}
        void clear(){
            for(int i=1;i<=m;++i){
                for(int j=1;j<=n;++j){
                    a[i][j]=0;
                }
            }
        }
        ll*operator[](int d){return a[d];}
    };
    
    mat operator*(mat a,mat b){
        mat c(a.m,b.n);
        //a.n==b.m
        c.clear();
        for(int k=1;k<=a.n;++k){
            for(int i=1;i<=a.m;++i){
                for(int j=1;j<=b.n;++j){
                    c[i][j]+=mul(a[i][k],b[k][j]);
                    c[i][j]%=mod;
                    if(c[i][j]<0)c[i][j]+=mod;
                }
            }
        }
        return c;
    }
    
    mat operator^(mat x,ll p){
        if(p==1)return x;
        if(p==2)return x*x;
        mat t=x^(p/2);
        t=t*t;
        if(p&1)t=t*x;
        return t;
    }
    
    
    int main(){
        ll m,a,c,x0,n,g;
        GetI64(m);GetI64(a);GetI64(c);GetI64(x0);GetI64(n);GetI64(g);
        mod=m;
        mat b(1,2);
        b[1][1]=x0;
        b[1][2]=c;
        mat f(2,2);
        f[1][1]=a;
        f[1][2]=0;
        f[2][1]=1;
        f[2][2]=1;
        mat ans=b*(f^n);
        ll x=ans[1][1]%g;
        if(x<0)x+=g;
        PutI64(x,"\n");
        return 0;
    }
       
    
  • 1
    @ 2014-07-04 22:59:27

    #include <iostream>
    #include <algorithm>
    #include <cstring>

    using namespace std ;

    #define ll long long

    ll m , a , c , n , g , x ;

    ll multi( ll y , ll cnt ) {
    if ( ! cnt ) return 0 ;
    if ( cnt == 1 ) return y % m ;
    ll rec = multi( y , cnt / 2 ) ;
    rec = ( rec + rec ) % m ;
    if ( cnt % 2 ) rec = ( rec + y ) % m ;
    return rec ;
    }

    struct maxtrix {
    ll a[ 2 ][ 2 ] ;
    maxtrix( ) {
    memset( a , 0 , sizeof( a ) ) ;
    }
    void print( ) {
    for ( int i = 0 ; i < 2 ; i ++ ) {
    for ( int j = 0 ; j < 2 ; j ++ ) {
    cout << a[ i ][ j ] << " " ;
    }
    cout << endl ;
    }
    }
    };

    maxtrix Multi( maxtrix m1 , maxtrix m2 ) {
    maxtrix rec ;
    for ( int i = 0 ; i < 2 ; i ++ ) {
    for ( int j = 0 ; j < 2 ; j ++ ) {
    for ( int k = 0 ; k < 2 ; k ++ ) {
    rec.a[ i ][ j ] += multi( m1.a[ i ][ k ] , m2.a[ k ][ j ] ) ;
    rec.a[ i ][ j ] %= m ;
    }
    }
    }
    return rec ;
    }

    maxtrix Pow( maxtrix x , ll cnt ) {
    if ( cnt == 1 ) return x ;
    maxtrix rec = Pow( x , cnt / 2 ) ;
    rec = Multi( rec , rec ) ;
    if ( cnt % 2 ) rec = Multi( rec , x ) ;
    return rec ;
    }

    int main( ) {
    cin >> m >> a >> c >> x >> n >> g ;
    maxtrix m1 , m2 ;
    m2.a[ 0 ][ 0 ] = a , m2.a[ 0 ][ 1 ] = 0 , m2.a[ 1 ][ 0 ] = c , m2.a[ 1 ][ 1 ] = 1 ;
    m1.a[ 0 ][ 0 ] = x , m1.a[ 0 ][ 1 ] = 1 ;
    maxtrix ans = Multi( m1 , Pow( m2 , n ) ) ;
    cout << ans.a[ 0 ][ 0 ] % g << endl ;
    return 0 ;
    }

  • 0
    @ 2016-12-27 19:10:38

    似乎可以不用要矩阵乘法吧……
    为什么当初我看到这道题第一感觉就是推式子……
    不过好像也可以做的样子……
    (其实现在我也觉得是矩乘

  • 0
    @ 2014-07-01 21:33:26

    使用矩阵乘法和快速幂,而且需要快速乘法。解题报告里有详细的矩阵乘法的推导。

  • 0
    @ 2013-12-06 21:33:31

    基本思路矩阵+快速幂

    当然这道题可能存在通项公式,而大牛可能可以求出通项公式。但这个对于普通大多数人不适合……
    快速幂的思想不仅要和矩阵相结合,而且乘法也需要。因为long long直接乘肯定爆

    构建矩阵

    1. x0 c

    2. a 0
      1 1
      其中第2个要n次方然后乘第一个,为了方便我的矩阵乘法是针对第2个矩阵的,第一个的至于第1个乘以第2个,就直接在print里弄了。so愿大家不要打我……
      另外友情提醒,**vijos输入输出long long要用%I64d,不是标准的%lld**
      %I64d
      还有不要提交错题目了,我就是(貌似这有点sb)……
      这是代码。可能不是很好

      code

      #include<stdio.h>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #define N 2
      #define M 2
      #define MAX_NUM 1000000000
      long long MU,g,c,a,n,x0;
      typedef long long matrix[N][M];
      matrix base,result,tmp1,tmp2;
      long long t;
      long long mytime(long long a,long long b)
      {
      if ((a <= MAX_NUM) && (b <= MAX_NUM))
      return (a*b)%MU;
      if ((b < 10) || (a < 10))
      return (a*b)%MU;
      if (a > b) {
      t = a; a = b; b = t;
      }
      t = mytime(b>>1,a);
      t = (t*2)%MU;
      if (b&1)
      t = (t+a)%MU;
      return t;
      }

      void mtime(long long *a,long long *b,long long r)
      {
      int static i,j,k;
      for (i = 0;i < N;i++)
      for (j = 0;j < M;j++) {
      for (k = 0,tmp2[i][j] = 0;k < M;k++)
      tmp2[i][j] = (tmp2[i][j]+mytime(
      (a+i*M+k),*(b+k*M+j)))%MU;
      }
      for (i = 0;i < N;i++)
      for (j = 0;j < M;j++)
      *r++ = tmp2[i][j];
      }

      void power(long long *base,long long n,long long *result)
      {
      int static i,j;
      if (n == 1) {
      for (i = 0;i < N;i++)
      for (j = 0;j < M;j++)
      *result++ = *base++;
      return;
      }
      if (n&1) {/*odd*/
      power(base,n>>1,result);
      mtime(result,result,tmp1[0]);
      mtime(tmp1[0],base,result);
      } else {
      power(base,n>>1,tmp1[0]);
      mtime(tmp1[0],tmp1[0],result);
      }
      }
      void print()
      {
      long long ans,tmp;
      ans = 0;
      tmp = mytime(x0,result[0][0]);
      ans = mytime(c,result[1][0]);
      ans = (tmp+ans)%MU;
      ans %= g;
      printf("%I64d",ans);
      }
      int main()
      {

      void init();

      init();
      power(base[0],n,result[0]);
      print();
      return 0;
      }

      void init()
      {
      scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&MU,&a,&c,&x0,&n,&g);
      a %= MU; c %= MU;
      base[0][0] = a; base[0][1] = 0;
      base[1][0] = 1; base[1][1] = 1;
      }

  • 0
    @ 2012-10-31 17:53:18

    有接触过矩阵乘法的就会觉得比较简单了

    这题难在两个大数相乘的时候可能会超过INT64而爆

    有一种方法可以在logn的时间内得到a*b mod m

    贴一下代码

    function c(a,b:int64):int64;

    begin

    c:=0;

    while b>0 do begin

    if b mod 2=1 then

    c:=(c+a) mod m else

    a:=(a+a) mod m;

    b:=b div 2; 

    end;

    end;

    • @ 2013-02-15 10:47:31

      去掉else就完美了

  • 0
    @ 2012-09-21 20:58:14

    矩阵

    除出题人外第一A!!!

  • -1
    @ 2016-07-02 20:42:40

    五十分乱搞,50-85分快速幂没打好,最后15分要让a*b mod m不爆掉,猎奇的cal函数,不解释,自己看。
    交了4次才A,感觉智商下降了,矩阵一开始构造错了。
    type arr=array[1..2,1..2]of int64;
    var
    j,k,o,p,n,m:int64;
    c,g,i,a:int64;
    x:int64;
    a1,b1:arr;
    function cal(x,y:int64):int64;
    var
    ans:int64;
    temp:int64;
    begin
    ans:=0;
    temp:=x;
    while y<>0 do
    begin
    if y and 1=1 then ans:=(ans+temp)mod m;
    temp:=(temp+temp)mod m;
    y:=y shr 1;
    end;
    exit(ans);
    end;
    function mul(a,b:arr;var c:arr):arr;
    var
    k,i,j:longint;
    begin
    fillchar(c,sizeof(c),0);
    for i:=1 to 2 do
    for j:=1 to 2 do
    begin
    for k:=1 to 2 do
    c[i,j]:=(c[i,j]+cal(a[i,k],b[k,j]))mod m;
    end;
    exit(c);
    //a1:=c;
    end;
    begin
    readln(m,a,c,x,n,g);
    a1[1,1]:=x;
    a1[1,2]:=1;
    b1[1,1]:=a;
    b1[2,1]:=c;
    b1[2,2]:=1;
    while n<>0 do
    begin
    if n and 1=1 then
    mul(a1,b1,a1);
    mul(b1,b1,b1);
    n:=n>>1;
    end;
    writeln(a1[1,1] mod g);
    end.

  • -1
    @ 2015-11-21 23:50:25

    矩阵乘法非常显然,但是后三个数据longlong一乘就爆了,所以用了一种诡异的方法解决了这个问题.......
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>

    using namespace std;

    long long m, a, c, x, n, g;
    long long origin[2][2], temp[2][2], b[2][2];

    int xx[64];

    long long mod(long long p, long long q) {
    for (int i = 0; i <= 62; ++i) {
    xx[i] = p & 1;
    p >>= 1;
    }
    long long ans = 0;
    for (int i = 0; i <= 62; ++i) {
    if (xx[i] & 1) {
    long long z = q;
    for (int j = 1; j <= i; ++j) {
    z *= 2;
    z %= m;
    }
    ans += z;
    ans %= m;
    }
    }
    return ans;
    }
    void pow0(long long k) {
    if (k == 1) {
    memcpy(b, origin, sizeof (b));
    return;
    }
    if (k & 1) {
    pow0(k - 1);
    memcpy(temp, b, sizeof (b));
    for (int i = 0; i < 2; ++i) {
    for (int k = 0; k < 2; ++k) {
    b[i][k] = ((mod(origin[i][0], temp[0][k]) % m) + mod(origin[i][1], temp[1][k]) % m) % m;
    }
    }
    }
    else {
    pow0(k / 2);
    memcpy(temp, b, sizeof (b));
    for (int i = 0; i < 2; ++i) {
    for (int k = 0; k < 2; ++k) {
    b[i][k] = ((mod(temp[i][0], temp[0][k]) % m) + mod(temp[i][1], temp[1][k]) % m) % m;
    }
    }
    }
    }
    int main(int argc, const char *argv[]) {
    scanf("%lld %lld %lld %lld %lld %lld", &m, &a, &c, &x, &n, &g);
    origin[0][0] = a % m;
    origin[0][1] = c % m;
    origin[1][1] = 1;
    pow0(n);
    printf("%lld\n", ((mod(x, b[0][0]) + b[0][1]) % m) % m % g);
    return 0;
    }

  • -1
    @ 2015-11-03 21:01:47

    P1725随机数生成器 Accepted
    记录信息
    评测状态 Accepted
    题目 P1725 随机数生成器
    递交时间 2015-11-03 21:01:19
    代码语言 C++
    评测机 Jtwd2
    消耗时间 41 ms
    消耗内存 508 KiB
    评测时间 2015-11-03 21:01:21
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 480 KiB, score = 5
    测试数据 #1: Accepted, time = 15 ms, mem = 476 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 480 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 480 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 476 KiB, score = 5
    测试数据 #5: Accepted, time = 0 ms, mem = 484 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 480 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 484 KiB, score = 5
    测试数据 #8: Accepted, time = 0 ms, mem = 480 KiB, score = 5
    测试数据 #9: Accepted, time = 0 ms, mem = 484 KiB, score = 5
    测试数据 #10: Accepted, time = 11 ms, mem = 496 KiB, score = 5
    测试数据 #11: Accepted, time = 0 ms, mem = 496 KiB, score = 5
    测试数据 #12: Accepted, time = 0 ms, mem = 500 KiB, score = 5
    测试数据 #13: Accepted, time = 0 ms, mem = 500 KiB, score = 5
    测试数据 #14: Accepted, time = 0 ms, mem = 500 KiB, score = 5
    测试数据 #15: Accepted, time = 0 ms, mem = 508 KiB, score = 5
    测试数据 #16: Accepted, time = 15 ms, mem = 504 KiB, score = 5
    测试数据 #17: Accepted, time = 0 ms, mem = 500 KiB, score = 5
    测试数据 #18: Accepted, time = 0 ms, mem = 504 KiB, score = 5
    测试数据 #19: Accepted, time = 0 ms, mem = 504 KiB, score = 5
    Accepted, time = 41 ms, mem = 508 KiB, score = 100
    代码
    #include <iostream>
    #include <stdio.h>
    #include <string.h>

    using namespace std;

    unsigned long long m , a , c , x , n , g;

    inline unsigned long long mul( unsigned long long a , unsigned long long b )
    {
    if( !b ) return 0;
    if( b & 1 ) return ( mul( a , b - 1 ) + a ) % m;
    unsigned long long t = mul( a , b >> 1 );
    return ( t << 1 ) % m;
    }

    struct matrix
    {
    unsigned long long mat[2][2];
    matrix( unsigned long long a , unsigned long long b , unsigned long long c , unsigned long long d )
    {
    mat[0][0] = a , mat[0][1] = b , mat[1][0] = c , mat[1][1] = d;
    }
    matrix() {}
    };

    inline matrix operator * ( matrix a , matrix b )
    {
    matrix c;
    memset( c.mat , 0 , sizeof( c.mat ) );
    for( register int k = 0 ; k < 2 ; k++ )
    for( register int i = 0 ; i < 2 ; i++ )
    for( register int j = 0 ; j < 2 ; j++ )
    c.mat[i][j] += mul( a.mat[i][k] , b.mat[k][j] ) , c.mat[i][j] %= m;
    return c;
    }

    matrix power( long long x )
    {
    if( !x ) return matrix( 1 , 0 , 0 , 1 );
    if( x & 1 ) return matrix( a , 0 , 1 , 1 ) * power( x - 1 );
    matrix a = power( x >> 1 );
    return a * a;
    }

    int main()
    {
    cin >> m >> a >> c >> x >> n >> g;
    matrix ans = power( n );
    cout << ( matrix( x , c , 0 , 0 ) * ans ).mat[0][0] % g << endl;
    return 0;
    }

  • -1
    @ 2014-12-27 21:04:18

    var
    fan:array[1..2,1..2] of int64;
    ans,x,i,m,a,c,n,g:int64;
    function plus(aa,bb:int64):int64;
    var tt,yy:int64;

    begin
    tt:=0 ;
    yy:=aa;
    while bb<>0 do
    begin
    if (bb and 1)=1 then

    tt:=(tt+yy) mod m;

    yy:=(yy+yy) mod m;
    bb:=bb shr 1;
    end;
    exit(tt);

    end;

    procedure quick(b:int64);
    var t,y:array[1..2,1..2] of int64;
    begin
    t[1,1]:=1;
    t[1,2]:=0;
    t[2,1]:=0;
    t[2,2]:=1;
    y:=fan;
    while b<>0 do
    begin
    if (b and 1 )=1 then
    begin

    t[1,2]:=(plus(t[1,1],y[1,2])mod m + t[1,2] mod m) mod m;
    t[1,1]:=plus(t[1,1],y[1,1] )mod m;
    end;

    y[1,2]:=(plus(y[1,1],y[1,2])mod m + y[1,2] mod m )mod m ;
    y[1,1]:=plus(y[1,1],y[1,1])mod m;

    b:=b shr 1;
    end;
    //writeln(t[1,1],'--',t[1,2]);
    fan:=t;
    end;

    begin
    // assign(input,'1725.in');
    // reset(input);
    readln(m,a,c,x,n,g);
    fan[1,1]:=a;
    fan[1,2]:=1;
    fan[2,1]:=0;
    fan[2,2]:=1;
    quick(n);
    ans:=((plus(fan[1,1],x) mod m +plus(fan[1,2],c) mod m) mod m )mod g;
    writeln(ans);

    end.

  • -1
    @ 2014-10-14 18:05:03

    program pro;
    type mine=array[1..2,1..2]of int64;
    var
    m,a,c,x0,n,g:int64;
    ans,matrix:mine;
    i,j:longint;

    function cal(x,y:int64):int64;
    var
    ans:int64;
    temp:int64;
    begin
    ans:=0;
    temp:=x;
    while y<>0 do
    begin
    if y and 1=1 then ans:=(ans+temp)mod m;
    temp:=(temp+temp)mod m;
    y:=y shr 1;
    end;
    exit(ans);
    end;

    procedure matrixc(x,y:mine; var z:mine);
    var
    ii,jj,kk:longint;
    begin
    fillchar(z,sizeof(z),0);
    for ii:=1 to 2 do
    for jj:=1 to 2 do
    for kk:=1 to 2 do
    z[ii,jj]:=(z[ii,jj]+cal(x[ii,kk],y[kk,jj]))mod m;
    end;

    begin
    readln(m,a,c,x0,n,g);
    matrix[1,1]:=a;
    matrix[1,2]:=0;
    matrix[2,1]:=c;
    matrix[2,2]:=1;
    ans[1,1]:=x0; ans[1,2]:=1;
    while n<>0 do
    begin
    if n and 1=1 then matrixc(ans,matrix,ans);
    matrixc(matrix,matrix,matrix);
    n:=n shr 1;
    end;
    writeln(ans[1,1]mod g);
    end.

  • 1

信息

ID
1725
难度
6
分类
其他 | 数学递推 | 线性代数 | 矩阵乘法 点击显示
标签
递交数
1074
已通过
254
通过率
24%
被复制
1
上传者