有关矩阵的模板【模板】

2019-04-14 20:26发布生成海报

站内文章 / 模拟电子

11506 0

#include <stdlib.h>
#include<stdio.h>
#include<string.h>

/*
矩阵最大的维数，比如你可能用到100*100的矩阵，那就定义这么大，虽然实际上用到的可能小一点。
 */
#define MAX_DIMENSION 10
/*
矩阵每个元素的类型。
 */
typedef int MATRIX_TYPE;
/*
矩阵乘法运算时和加法运算时，为避免溢出，在取模之前用这个类型暂存。
 */
typedef long long MAX_INT_TYPE; //temporary var to avoid overflowing
/*
矩阵类型的定义。
 */
typedef MATRIX_TYPE Matrix[MAX_DIMENSION][MAX_DIMENSION];
/*
实际运算时矩阵的维数，注意在这个模板中这是全局变量，也就是说有矩阵的维数都是一样的。
你可以在程序中设置，以符合你的需求，但是不能超过MAX_DIMENSION
 */
int ndim=MAX_DIMENSION;
/*
程序会判断是否需要取模，如果为<1的值，那么不取模运算，否则运算结果 矩阵加法 乘法中有取模。
可在程序中设置这个变量的值
 */
int mod=1; //mod

void m_zero(Matrix x)
{
  memset(x, 0, sizeof (MATRIX_TYPE) * MAX_DIMENSION * MAX_DIMENSION);
}

void m_one(Matrix x)
{
  int i;
  m_zero(x);
  for (i=0; i < ndim; ++i)x[i][i]=1;
}

void m_copy(Matrix src, Matrix dest)
{
  memcpy(dest, src, sizeof (MATRIX_TYPE) * MAX_DIMENSION * MAX_DIMENSION);
}
//z=x+y;

void m_add(Matrix x, Matrix y, Matrix z)
{
  int i, j;
  for (i=0; i < ndim; i++)
    for (j=0; j < ndim; j++)
      if (mod <= 1)z[i][j]=x[i][j] + y[i][j];
      else z[i][j]=(x[i][j]+(MAX_INT_TYPE) y[i][j]) % mod; //module
}
//c=a*b

void m_multiple(Matrix a, Matrix b, Matrix c)
{
  int i, j, k;
  MAX_INT_TYPE t;

for (i=0; i < ndim; i++)
    for (j=0; j < ndim; j++)
    {
      t=0;
      if (mod <= 1)
        for (k=0; k < ndim; k++) t+=a[i][k] * b[k][j]; //module
      else
        for (k=0; k < ndim; k++)
        {
          t+=(a[i][k]*(MAX_INT_TYPE) b[k][j]) % mod;
          t%=mod;
        }//module
      c[i][j]=t;
    }
}
//y=x^n

void m_pow(Matrix x, unsigned int n, Matrix y)
{
  Matrix temp, temp_x;
  m_one(y);
  m_copy(x, temp_x);
  for (; n;)
  {
    if ((n & 1) != 0)
    {
      m_multiple(temp_x, y, temp);
      m_copy(temp, y);
    }
    if ((n>>=1))
    {
      m_multiple(temp_x, temp_x, temp);
      m_copy(temp, temp_x);
    }
  }
}

//根据已经算出来的x^1 x^2 x^4 ...去求矩阵的幂y=x^n

void m_pow_with_saved(Matrix x_p[], unsigned int n, Matrix y)
{
  Matrix temp;
  m_one(y);
  for (int k=1; n; ++k, n>>=1)
  {
    if ((n & 1) != 0)
    {
      m_multiple(x_p[k], y, temp);
      m_copy(temp, y);
    }
  }
}

//计算根据已经算出来的x^1 x^2 x^4 ...去求矩阵的幂和y=sum(x^n)

void m_pow_sum1(Matrix x_p[], unsigned int n, Matrix y)
{
  m_zero(y);
  if (n == 0)return;
  if (n == 1) m_copy(x_p[1], y);
  else
  {
    Matrix temp;
    //calculate x^1+...+^(n/2)
    m_pow_sum1(x_p, n >> 1, temp);
    //add to y
    m_add(temp, y, y);
    //calculate x^(1+n/2)+...+x^n
    Matrix temp2;
    m_pow_with_saved(x_p, n >> 1, temp2);
    Matrix temp3;
    m_multiple(temp, temp2, temp3);
    //add to y
    m_add(temp3, y, y);
    if (n & 1)
    {
      //calculate x^(n-1)
      m_multiple(temp2, temp2, temp3);
      //calculate x^n
      m_multiple(temp3, x_p[1], temp2);
      //add x^n
      m_add(temp2, y, y);
    }
  }

}
//计算x^1 x^2 x^4 ...，然后调用求幂和的地方

void m_pow_sum(Matrix x, unsigned int n, Matrix y)
{
  //calculate x^1 x^2 x^4 ... x^logn
  unsigned int i=0, logn, n2=n;
  for (logn=0, n2=n; n2; logn++, n2>>=1);
  Matrix *pow_arry=new Matrix[logn == 0 ? 2 : (logn + 1)];
  m_one(pow_arry[0]);
  m_copy(x, pow_arry[1]);
  for (i=1; i < logn; i++)
  {
    m_multiple(pow_arry[i], pow_arry[i], pow_arry[i + 1]);
  }

m_pow_sum1(pow_arry, n, y);
  delete []pow_arry;
}

void m_out(Matrix x)
{
  int i, j;
  for (i=0; i < MAX_DIMENSION; i++)
  {
    for (j=0; j < MAX_DIMENSION; j++)
      printf("%d ", x[i][j]);
    printf("/n");
  }

}

int main()
{
  Matrix mm={
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
  };
  Matrix y;
  int k, m, i;
  int sum;
  while (scanf("%d%d", &k, &m) != EOF)
  {
    
    for (i=0; i < 10; i++)
      scanf("%d", &mm[0][i]);
    if (k < 10)
    {
      printf("%d/n", k%m);
      continue;
    }
    mod=m;
    m_pow(mm, k - 9, y);
    sum=0;
    for (i=0; i < 10; i++)
      sum+=y[0][i]*(9 - i);
    printf("%d/n", sum % m);
  }
  return 0;
}

有关矩阵的模板【模板】

Ta的文章更多 >>

热门文章

有关矩阵的模板【模板】

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

Ta的文章更多 >>