题意：给你一个二元组，求这个二元组的最长上升子序列，并且记录路径
解题思路：一个值从小到大排序，在这个值相等的情况情况下按从大到小排序（为了不取到第一个值相等），然后对第二个值 求一个最长上升自诩，路径的话求实求最长上升子序列的时候 记录 来自前一个值。
解题代码：
1 // File Name: e.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月21日 星期六 19时58分58秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int M , n ; 28 struct Matrix 29 { 30 int mat[40][40]; 31 void clear() 32 { 33 memset(mat,0,sizeof(mat)); 34 } 35 void output() 36 { 37 for(int i = 0 ;i < n;i ++) 38 { 39 for(int j = 0 ;j < n;j ++) 40 { 41 printf("%d ",mat[i][j]); 42 } 43 printf(" "); 44 } 45 } 46 Matrix operator *(const Matrix &b) const 47 { 48 Matrix ret; 49 ret.clear(); 50 for(int i = 0 ;i < n;i ++) 51 for(int j = 0 ;j < n;j ++) 52 { 53 for(int s = 0 ; s < n; s ++) 54 { 55 ret.mat[i][j] = (ret.mat[i][j] + mat[i][s] *b.mat[s][j] % M) % M; 56 } 57 } 58 return ret; 59 } 60 }a; 61 char str[1000]; 62 int num[1000]; 63 int len ; 64 int t; 65 void judge(int x, int y) 66 { 67 //printf("%d %d*** ",x,y); 68 int tx = x; 69 int ty = y; 70 int ttt = 0 ; 71 int txa[10]; 72 int tya[10]; 73 memset(txa,0,sizeof(txa)); 74 memset(tya,0,sizeof(tya)); 75 while(tx) 76 { 77 txa[ttt] = tx % 2; 78 tx/= 2; 79 ttt++; 80 } 81 ttt =0 ; 82 while(ty) 83 { 84 tya[ttt] = ty % 2; 85 ty /= 2; 86 ttt++; 87 } 88 for(int i = 1;i < t; i ++) 89 if(tya[i]+tya[i-1]+txa[i] + txa[i-1] == 4 || tya[i] + tya[i-1] + txa[i] + txa[i-1] == 0 ) 90 { 91 return; 92 } 93 a.mat[x][y] = 1; 94 } 95 void jian() 96 { 97 for(int i= 0 ;i <= len/2;i ++) 98 { 99 swap(num[i],num[len-i]); 100 } 101 for(int i = 0 ;i <= len ;i ++) 102 { 103 if(num[i] == 0 ) 104 { 105 num[i] = 9 ; 106 }else{ 107 num[i]-- ; 108 break; 109 } 110 } 111 /*for(int i = len ;i >= 0 ;i --) 112 printf("%d",num[i]); 113 printf(" ");*/ 114 if(num[len] == 0 ) 115 len --; 116 /* 117 for(int i = len ;i >= 0 ;i --) 118 printf("%d",num[i]); 119 printf(" ");*/ 120 } 121 void chu() 122 { 123 int tmp = 0 ; 124 for(int i = len ;i >= 0 ;i --) 125 { 126 int k = (tmp * 10 + num[i]); 127 num[i] = k/2; 128 tmp = k % 2; 129 } 130 if(num[len] == 0 ) 131 len --; 132 /* 133 for(int i = len ;i >= 0 ;i --) 134 printf("%d",num[i]); 135 printf(" ");*/ 136 } 137 Matrix Pow(Matrix a) 138 { 139 Matrix ret; 140 ret.clear(); 141 for(int i= 0 ;i < n;i ++) 142 ret.mat[i][i] = 1; 143 Matrix tmp = a; 144 while(len != -1) 145 { 146 // printf("%d *** ",len); 147 if(num[0] % 2 == 1) 148 { 149 ret = ret * tmp ; 150 //ret.output(); 151 } 152 tmp = tmp*tmp ; 153 chu(); 154 } 155 return ret; 156 } 157 int main(){ 158 freopen("nice.in","r",stdin); 159 freopen("nice.out","w",stdout); 160 161 scanf("%s %d %d",str,&t,&M); 162 len = strlen(str); 163 for(int i= 0 ;i < len ;i ++) 164 { 165 num[i] = str[i] - '0'; 166 } 167 len --; 168 n = (1 << t); 169 for(int i = 0 ;i <n ;i ++) 170 { 171 for(int j = 0 ;j < n;j ++) 172 { 173 judge(i,j); 174 } 175 } 176 // a.output(); 177 jian(); 178 a = Pow(a); 179 //a.output(); 180 int sum = 0 ; 181 for(int i = 0 ;i < n;i ++) 182 for(int j = 0 ;j < n;j ++) 183 { 184 sum = (sum + a.mat[i][j]) % M; 185 } 186 printf("%d ",sum); 187 188 return 0; 189 }