集合：具有共同性质的或合适一定条件的事物的全体，组成集合的这些个体成为元素。
 集合之间常见的关系：包含（⊆），真包含（⊂），相等（=）。
 笛卡尔积：设A,B为集合，以A中元素为第一元素，B中元素为第二元素构成有序对，所以这样的有序对组成的集合称为A与B的笛卡尔积，记作A×B。用符号化表示：A×B={<x,y>|x∈A∧y∈B}
 
 对关系图的表示方法，一共有三种，简单的是集合，另外有两种，矩阵和关系图。
 
 例题：
 那么我们之前介绍了集合和关系R，那么现在介绍关系的n次幂。
 设R为A上的关系，n为自然数，则R的n次幂定义：
 (1)Rº={<x,x>|x∈A}
 (2)?^(?+1)=?ⁿ ∘R
 
 

 
 
 
 
版权声明：所有的笔记，可能来自很多不同的网站和说明，在此没法一一列出，如有侵权，请告知，立即删除。 

 
文章目录
 
一、关系幂运算
二、关系幂运算示例
三、关系幂运算性质

 

 

 

 

 
一、关系幂运算
 
 

 
关系 $R$ 的 $n$ 次幂定义 :
 
$R\subseteq A\times A,n\in N$
 
$\{\begin{array}{ll}{R}^0=I_A& \\ R^{n+1}=R^n\circ R& (n\ge 0)\end{array}$
 

 
关系 $R$ 是 集合 $A$ 上的 二元关系 , $R$ 的 $0$ 次幂 $R^0$ 是恒等关系 $I_A$ , 关系 $R$ 的 $n+1$ 次幂等于 $R^{n+1}=R^n\circ R$ 其中 $n\ge 0$ ;
 
$R^1=R^0\circ R=R$ , 恒等关系与 关系 $R$ 逆序合成 , 结果还是关系 $R$ , 这个关系 $R$ 可以是任意关系 ;
 
恒等关系就是 集合 $A$ 中每个元素自己跟自己有关系 ;
 
关系 $R$ 幂运算结果 $R^n$ 关系 也是集合 $A$ 上的二元关系 , 因此有 $R^n\subseteq A\times A$
 

 

 
关系 $R$ 的 $n$ 次幂 , 就是 $n$ 个 $R$ 关系逆序合成 :
 
$R^n=\begin{array}{c}\underbrace{R\circ R\circ \cdots \circ R}\\ n个R逆序合成\end{array}$
 

 

 

 

 
二、关系幂运算示例
 
 

 
集合 
     
      
       
        
         A
        
        
         =
        
        
         {
        
        
         a
        
        
         ,
        
        
         b
        
        
         ,
        
        
         c
        
        
         }
        
       
       
        A = \{ a, b, c \}
       
      
     A={a,b,c} 关系 $R$ 是 集合 $A$ 上的二元关系 , $R\subseteq A\times A$ ,
 

    
     
      
       
        R
       
       
        =
       
       
        {
       
       
        <
       
       
        a
       
       
        ,
       
       
        b
       
       
        >
       
       
        ,
       
       
        <
       
       
        b
       
       
        ,
       
       
        a
       
       
        >
       
       
        ,
       
       
        <
       
       
        a
       
       
        ,
       
       
        c
       
       
        >
       
       
        }
       
      
      
       R = \{ <a,b> , <b,a> , <a, c> \}
      
     
    R={<a,b>,<b,a>,<a,c>}
 

 
关系 $R$ 的 幂集个数 : $A$ 是有限集 , $A$ 上的有序对个数是 $3\times 3=9$ 个 , $A$ 上的二元关系个数 , 即有序对集合的幂集个数 , 是 $2^{3\times 3}=512$ 个 ;
 

 

 
关系 $R$ 的 $0$ 次幂 : $R^0=I_A$ , $R$ 关系的 $0$ 次幂是恒等关系 , 关系图是每个顶点都有环 , 顶点之间没有关系 ;
 
 

 

 
关系 $R$ 的 $1$ 次幂 : $R^1=R^0\circ R=R$ , 恒等关系 $I_A$ 与任何关系逆序合成 , 结果还是那个关系 ;
 
 

 

 
关系 $R$ 的 $2$ 次幂 :
 

     
      
       
        
         
          
           
            
             R
            
            
             2
            
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             
              R
             
             
              0
             
            
            
             ∘
            
            
             R
            
           
          
         
        
        
         
          
           
          
         
        
        
         
          
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             R
            
            
             ∘
            
            
             R
            
           
          
         
        
        
         
          
           
          
         
        
        
         
          
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             {
            
            
             <
            
            
             a
            
            
             ,
            
            
             b
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             a
            
            
             >
            
            
             ,
            
            
             <
            
            
             a
            
            
             ,
            
            
             c
            
            
             >
            
            
             }
            
            
             ∘
            
            
             {
            
            
             <
            
            
             a
            
            
             ,
            
            
             b
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             a
            
            
             >
            
            
             ,
            
            
             <
            
            
             a
            
            
             ,
            
            
             c
            
            
             >
            
            
             }
            
           
          
         
        
        
         
          
           
          
         
        
        
         
          
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             {
            
            
             <
            
            
             a
            
            
             ,
            
            
             a
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             b
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             c
            
            
             >
            
            
             }
            
           
          
         
        
       
       
        \begin{array}{lcl}R^2 & = & R^0 \circ R \\\\ &=& R \circ R \\\\ &=& \{ <a,b> , <b,a> , <a, c> \} \circ \{ <a,b> , <b,a> , <a, c> \} \\\\ &=& \{ <a,a>, <b, b> , <b,c> \}\end{array}
       
      
     R2​====​R0∘RR∘R{<a,b>,<b,a>,<a,c>}∘{<a,b>,<b,a>,<a,c>}{<a,a>,<b,b>,<b,c>}​
 
注意上述 $\circ$ 运算时逆序合成 , 从后面的关系中合成前面的关系 ;
 
 

 

 
关系 $R$ 的 $3$ 次幂 : 与 $R_1$ 相同
 

     
      
       
        
         
          
           
            
             R
            
            
             3
            
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             
              R
             
             
              1
             
            
            
             ∘
            
            
             R
            
           
          
         
        
        
         
          
           
          
         
        
        
         
          
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             {
            
            
             <
            
            
             a
            
            
             ,
            
            
             a
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             b
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             c
            
            
             >
            
            
             }
            
            
             ∘
            
            
             {
            
            
             <
            
            
             a
            
            
             ,
            
            
             b
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             a
            
            
             >
            
            
             ,
            
            
             <
            
            
             a
            
            
             ,
            
            
             c
            
            
             >
            
            
             }
            
           
          
         
        
        
         
          
           
          
         
        
        
         
          
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             {
            
            
             <
            
            
             a
            
            
             ,
            
            
             b
            
            
             >
            
            
             ,
            
            
             <
            
            
             a
            
            
             ,
            
            
             c
            
            
             >
            
            
             ,
            
            
             <
            
            
             b
            
            
             ,
            
            
             a
            
            
             >
            
            
             }
            
           
          
         
        
        
         
          
           
          
         
        
        
         
          
           
          
         
         
          
           
            =
           
          
         
         
          
           
            
             R
            
            
             1
            
           
          
         
        
       
       
        \begin{array}{lcl}R^3 & = & R^1 \circ R \\\\ &=& \{ <a,a>, <b, b> , <b,c> \} \circ \{ <a,b> , <b,a> , <a, c> \} \\\\ &=& \{ <a,b>, <a, c> , <b,a> \} \\\\ &=& R^1 \end{array}
       
      
     R3​====​R1∘R{<a,a>,<b,b>,<b,c>}∘{<a,b>,<b,a>,<a,c>}{<a,b>,<a,c>,<b,a>}R1​
 
 

 

 
关系 $R$ 的 $4$ 次幂 : 与 $R_2$ 相同
 

 

 
关系 $R$ 的 $5$ 次幂 : 与 $R_1$ 相同
 

 

 
关系 $R$ 的 $2k$ 偶数次幂 ( $k=1,2,\cdots$ ) : 与 $R_2$ 相同
 

 

 
关系 $R$ 的 $2k+1$ 奇数次幂 ( $k=0,1,2,\cdots$ ) : 与 $R_1$ 相同
 

 

 

 

 
三、关系幂运算性质
 
 

 
关系幂运算性质 :
 
关系 $R$ 是 集合 $A$ 上的关系 , $R\subseteq A\times A$ , $m,n$ 是自然数 , $m,n\in N$ ; 关系幂运算有以下两个性质 :
 
$R^m\circ R^n=R^{m+n}$
 
$(R^m{)}^n=R^{mn}$

矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素的o（n）的时间复杂度，降到log（n）。
 
 
 这里先对原理（主要运用了矩阵乘法的结合律）做下简单形象的介绍：
 
 
 一般一个矩阵的n次方，我们会通过连乘n-1次来得到它的n次幂。
 
 
 但做下简单的改进就能减少连乘的次数，方法如下：
 
 
 把n个矩阵进行两两分组，比如：A*A*A*A*A*A  =>  (A*A)*(A*A)*(A*A)
 
 
 这样变的好处是，你只需要计算一次A*A，然后将结果(A*A)连乘自己两次就能得到A^6，即(A*A)^3=A^6。算一下发现这次一共乘了3次，少于原来的5次。
 
 
 其实大家还可以取A^3作为一个基本单位。原理都一样：利用矩阵乘法的结合律，来减少重复计算的次数。
 
 
 以上都是取一个具体的数来作为最小单位的长度，这样做虽然能够改进效率，但缺陷也是很明显的，取个极限的例子（可能有点不恰当，但基本能说明问题），当n无穷大的时候，你现在所取的长度其实和1没什么区别。所以就需要我们找到一种与n增长速度”相适应“的”单位长度“，那这个长度到底怎么去取呢？？？这点是我们要思考的问题。
 
 
 有了以上的知识，我们现在再来看看，到底怎么迅速地求得矩阵的N次幂。
 
 
 既然要减少重复计算，那么就要充分利用现有的计算结果咯！~怎么充分利用计算结果呢？？？这里考虑二分的思想。。
 
 
 大家首先要认识到这一点：任何一个整数N，都能用二进制来表示。。这点大家都应该知道，但其中的内涵真的很深很深（这点笔者感触很深，在文章的最后，我将谈谈我对的感想）！！
 
 
 计算机处理的是离散的信息，都是以0,1来作为信号的处理的。可想而知二进制在计算机上起着举足轻重的地位。它能将模拟信号转化成数字信号，将原来连续的实际模型，用一个离散的算法模型来解决。  好了，扯得有点多了，不过相信这写对下面的讲解还是有用的。
 
 
 回头看看矩阵的快速幂问题，我们是不是也能把它离散化呢？比如A^19  =>  （A^16）*（A^2）*（A^1），显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n)，不仅这样，因子间也是存在某种联系的，比如A^4能通过(A^2)*(A^2)得到，A^8又能通过(A^4)*(A^4)得到，这点也充分利用了现有的结果作为有利条件。下面举个例子进行说明：
 
 
 现在要求A^156,而156(10)=10011100(2) 
 
 
  
也就有A^156=>(A^4)*(A^8)*(A^16)*(A^128)  考虑到因子间的联系，我们从二进制10011100中的最右端开始计算到最左端。细节就说到这，下面给核心代码：
 

while(N)
 {
                if(N&1)
                       res=res*A;
                n>>=1;
                A=A*A;
 }
 
 
 
 里面的乘号，是矩阵乘的运算，res是结果矩阵。
 
 
 第3行代码每进行一次，二进制数就少了最后面的一个1。二进制数有多少个1就第3行代码就执行多少次。
 
 
 好吧，矩阵快速幂的讲解就到这里吧。在文章我最后给出我实现快速幂的具体代码（代码以3*3的矩阵为例）。
 
 
 现在我就说下我对二进制的感想吧：
 
 
 我们在做很多”连续“的问题的时候都会用到二进制将他们离散简化
 
 
 1.多重背包问题
 
 
 2.树状数组
 
 
 3.状态压缩DP
 
 
 ……………还有很多。。。究其根本还是那句话：化连续为离散。。很多时候我们并不是为了解决一个问题而使用二进制，更多是时候是为了优化而使用它。所以如果你想让你的程序更加能适应大数据的情况，那么学习学习二进制及其算法思想将会对你有很大帮助。
 
 
 最后贴出一些代码供大家学习，主要起演示的效果：
 
 
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream> 
using namespace std;

int N;

struct matrix
{
       int a[3][3];
}origin,res;


matrix multiply(matrix x,matrix y)
{
       matrix temp;
       memset(temp.a,0,sizeof(temp.a));
       for(int i=0;i<3;i++)
       {
               for(int j=0;j<3;j++)
               {
                       for(int k=0;k<3;k++)
                       {
                               temp.a[i][j]+=x.a[i][k]*y.a[k][j];
                       }
               }
       }
       return temp;
}

void init()
{
     printf("随机数组如下:\n");
     for(int i=0;i<3;i++)
     {
             for(int j=0;j<3;j++)
             {
                     origin.a[i][j]=rand()%10;
                     printf("%8d",origin.a[i][j]);
             }
             printf("\n");
     }
     printf("\n");
     memset(res.a,0,sizeof(res.a));
     res.a[0][0]=res.a[1][1]=res.a[2][2]=1;                  //将res.a初始化为单位矩阵 
}

void calc(int n)
{
     while(n)
     {
             if(n&1)
                    res=multiply(res,origin);
             n>>=1;
             origin=multiply(origin,origin);
     }
     printf("%d次幂结果如下：\n",n);
     for(int i=0;i<3;i++)
     {
             for(int j=0;j<3;j++)
                     printf("%8d",res.a[i][j]);
             printf("\n");
     }
     printf("\n");
}
int main()
{
    while(cin>>N)
    {
            init();
            calc(N);
    }
    return 0;
}