转载请注明出处，谢谢 by---cxlove
水水更健康，最终回到1800+了。。。
DIV2 1000pt
显然每一列是独立的。分开考虑。
对于某一列。假设按单个字符U ， D从下往上考虑的话。发现连续两个U的话。以下的U能够移动的位置受上面一个影响。
只是因此能够想到相邻的U ， D互相限制位置，能够依次处理。相邻同样字符的话。 能够作为一个字符。
做法：把相邻的U合并，相邻的D合并。dp[i][j]表示前i个部分处理完。第i个部分最靠上的一个位置为j。
这种话，假设当前为U。那么向上移动的最远位置为下一个部分最靠下的D的位置。
假设当前为D。那么向下移动的最远位置便是上一个部分最靠上的U的位置。
这样就能够搞出每个部分的上下界，然后分别DP。
typedef long long LL;const LL MOD = 1000000007;const int N = 55;LL dp[N][N];void add (LL &a , LL b) { a += b; a = (a % MOD + MOD) % MOD;}LL mut (LL a , LL b) { a = a * b % MOD; a = (a + MOD) % MOD; return a;}LL gao_up (vector &v , int limit) { int n = v.size(); LL c[N][N]; memset (c , 0 , sizeof(c)); c[n - 1][limit - 1] = 1; for (int i = n - 2 ; i >= 0 ; i --) { for (int j = limit ; j >= 0 ; j --) { if (c[i + 1][j] == 0) continue; for (int k = v[i] ; k < j ; k ++) { add (c[i][k] , c[i + 1][j]); } } } LL ans = 0; for (int i = 1 ; i <= limit ; i ++) { add (ans , c[0][i]); } return ans;}LL gao_down (vector &v , int down , int up) { int n = v.size(); LL c[N][N]; memset (c , 0 , sizeof(c)); c[0][down] = 1; for (int i = 0 ; i < n ; i ++) { for (int j = 0 ; j <= up ; j ++) { if (c[i][j] == 0) continue; for (int k = j + 1 ; k <= v[i] ; k ++) add (c[i + 1][k] , c[i][j]); } } return c[n][up];}vector > v;class FoxAndShogi {public:int differentOutcomes(vector board) { int row = board.size() , col = board[0].size(); LL ans = 1LL; for (int c = 0 ; c < col ; c ++) { memset (dp , 0 , sizeof(dp)); string s = ""; v.clear (); for (int r = row - 1 ; r >= 0 ; r --) s = s + board[r][c]; int first = -1; for (int i = 0 , pre = -1 ; i < s.size() ; i ++) { if (s[i] == '.') continue; if (s[i] == 'D' && pre == 0) { v[v.size() - 1].push_back (i + 1); } else if (s[i] == 'U' && pre == 1) { v[v.size() - 1].push_back (i + 1); } else { if (first == -1) { if (s[i] == 'U') first = 0; else first = 1; } vector t; t.push_back(i + 1); v.push_back(t); if ( s[i] == 'U') pre = 1; else pre = 0; } } dp[0][0] = 1; for (int i = 0 ; i < v.size() ; i ++) { for (int j = 0 ; j <= row ; j ++) { if (dp[i][j] == 0) continue; // up if ((first == 0 && i % 2 == 0) || (first == 1 && i % 2 == 1)){ int now = v[i][v[i].size() - 1]; int limit = (i + 1) < v.size() ? v[i + 1][0] : (col + 1); for (int k = now ; k < limit ; k ++) { add (dp[i + 1][k] , mut (dp[i][j] , gao_up (v[i] , k + 1))); } } //down else { int now = v[i][v[i].size() - 1]; for (int k = j + 1 ; k <= now ; k ++) { add (dp[i + 1][k] , mut (dp[i][j] , gao_down (v[i] , j , k))); } } } } LL tmp = 0; for (int i = 0 ; i <= row ; i ++) add (tmp , dp[v.size()][i]); // cout << tmp << endl; ans = mut (ans , tmp); } return ans;}}; DIV1 250PT 把L，R所有提取出来，先推断下是否一致。
然后 比較下位置
DIV1 500 PT
异或结果 小于等于LIMIT，先处理相等的情况，既异或结果每一位都和LIMIT相等，列方程组，求一下秩。
否则的话。必定存在某一位，LIMIT中为1。实际为0,并且高位和LIMIT一致，低位随意 。
所以枚举相隔的这个位置。相同是列方程组求解。
typedef long long LL;int a[100][100];int n , m ;long long gauss(){ int i,j,row=1,col; for (col=1;col<=m;++col){ for (i=row;i<=n;++i) if (a[i][col]) break ; if (i>n) continue ; if (i!=row){ for (j=col;j<=m;++j) swap(a[row][j],a[i][j]); swap(a[i][m + 1],a[row][m + 1]); } for (i=row+1;i<=n;++i) if (a[i][col]){ for (j=col;j<=m;++j) a[i][j]^=a[row][j]; a[i][m + 1]^=a[row][m + 1]; } ++row; } for (i=row;i<=n;++i) if (a[i][m + 1]) return 0; return 1ll<<(long long)(m-row+1); }class XorCards {public:long long numberOfWays(vector number, long long limit) { LL ans = 0; m = number.size();n = 61; memset (a , 0 , sizeof(a)); for (int i = 0 ; i < 61 ; i ++) { for (int j = 0 ; j < m ; j ++) { if (number[j] & (1LL << i)) a[i + 1][j + 1] = 1; } a[i + 1][m + 1] = (limit & (1LL << i)) ? 1 : 0; } ans = gauss (); for (int i = 0 ; i < 61 ; i ++) { if (!(limit & (1LL << i))) continue; memset (a , 0 , sizeof(a)); for (int j = i + 1 ; j < 61 ; j ++) { for (int k = 0 ; k < m ; k ++) { if (number[k] & (1LL << j)) a[j + 1][k + 1] = 1; } a[j + 1][m + 1] = (limit & (1LL << j)) ? 1 : 0; } for (int k = 0 ; k < m ; k ++) { if (number[k] & (1LL << i)) a[i + 1][k + 1] = 1; } ans += gauss (); } return ans;}}; DIV1 1000PT 排序方式价格优势，然后 镶上每次迭代暴力，folyd寻求最短的价格后，值。。
。