M序列

1. 信息安全

主要用在加密解密上面

2. 通信行业

CDMA通信的行业的信息

m序列是最长线性移位寄存器序列的简称，是一种伪随机序列、伪噪声(PN)码或伪随机码。可以预先确定并且可以重复实现的序列称为确定序列;既不能预先确定又不能重复实现的序列称随机序列;不能预先确定但可以重复产生的序列称伪随机序列。

m序列是目前广泛应用的一种伪随机序列，其在通信领域有着广泛的应用，如扩频通信，卫星通信的码分多址，数字数据中的加密、加扰、同步、误码率测量等领域。

在所有的伪随机序列中，m序列是最重要、最基本的一种伪随机序列。它容易产生，规律性强，有很好的自相关性和较好的互相关特性。在IS-95的反向信道中，选择了m序列的PN码作为地址码，利用不同相位m序列几乎正交的特性来为每个用户的业务信道分配了一个相位。

对于一个n级反馈移位寄存器来说，最多可以有2^n 个状态，对于一个线性反 馈移位寄存器来说，全"0"状态不会转入其他状态，所以线性移位寄存器的序列的最长周期为 2^n-1。当n级线性移位寄存器产生的序列{ai}的周期为T= 2^n-1时，称{ai}为n级m序列。

当反馈函数f(a1,a2,a3,…an)为非线性函数时，便构成非线性移位寄存器，其输出序列为非线性序列。输出序列的周期最大可达 2^n ，并称周期达到最大值的非线性移位寄存器序列为M序列。

最长上升子序列

Longest Increasing Subsequence

最长上升子序列:

有两种基本方法:两个时间复杂度分别为O(n^2)和O(nlogn)

对于给定数列a，元素个数为n，f[i]为以元素i结尾的最长子上升序列的最大长度。

最长上升子序列f满足对任意1<=j<i<=n(a[j]<a[i])，有f[j]<f[i]。

容易得出O(n^2)的DP状态转移方程:

f[i]=max{f[j]}+1;(1<=j<i且a[j]<a[i])

我们不妨把f的初值设为0，并在末尾添加一个元素inf，并将n++

这样经过两重循环，f[n]即为LIS长度

代码如下:

又称作CMI算法

时间复杂度为O(nlogn)

其操作如下:

开辟一个栈b，每次取栈顶元素s和读到的元素a做比较，如果a>s，则置为栈顶;如果a<s，则二分查找栈中的比a大的第1个数，并替换。最终栈的大小即为最长递增子序列为长度

考察b栈内每个元素的含义,b[i] 表示所有长度为i的上升子序列中最小的最后一个数.

·举例:原序列为3，4，5，2，4，2

栈为3，4，5，此时读到2，则用2替换3，得到栈中元素为2，4，5，再读4，用4替换5，得到2，4，4，再读2，得到最终栈为2，2，4,最终得到的解是:

长度为1的上升子序列中最小的最后一个数是2 (2)

长度为2的上升子序列中最小的最后一个数是2 (2,2)长度为3的上升子序列中最小的最后一个数是4 (3,4,4)

可知没有长度为4的上升子序列,最长递增子序列长度为3. (3,4,4)

CMI本质是LIS问题的另一种动态规划思路

注意:CMI只能求LIS的长度和最后一个数,不能求LIS的序列!

代码如下:

#include<iostream>

using namespace std;

int n;

int a[1001],b[1001];

int rear;

int solve(int t)

{ int l=1,r=rear;

while(l<=r)

{ int mid=(l+r)>>1;

if(b[mid]>=t)//若为非递减序列，则为b[mid]>t

r=mid-1;

else

l=mid+1;

}

if(l>rear)

rear=l;

return l;

}

int main()

{ int i,j;

scanf("%d",&n);

rear=0;

for(i=1;i<=n;i++)

{

scanf("%d",&a[i]);

b[solve(a[i])]=a[i];

}

printf("%d\n",rear);

system("pause");

return 0;

}