链接：http://codeforces.com/problemset/problem/319/A
题意：给出一个长度为n的01串表示一个数 x ，现在有2支队伍A，B分别有 2n 个队员，标号为 0，1，2，...，2n−1 , A中标号为 i 的队员和B中标号为 ix 的队员配对，求这些配对的复杂度，即所有配对中满足 在配对<a，b>和<c，d>有a<c，b>d ， 的配对组有多少组。简化为求逆序数对的个数。
分析：我们可以从 01 串入手，当n=1的时候，如果是单个0，复杂度为0；如果是单个1，复杂度为1。进一步思考：如果在一个长度为 n 的01串表示为 x 后增加一个0的话，即增加了 2n 个配对，又最后这个0是不会改变标号的最高位的数字的值，那么相当于与这一位异或不会影响到原来数的大小顺序，即对对应标号的大小无影响，所以新增加的 2n 个配对的复杂度还是和前面的01串有关，即新增加的配对的复杂度等于前n个01串的结果，然后总的复杂度*=2；如果在它后面增加一个1的话，首先还是和0一样，新增加的 2n 个配对中内部的复杂度还是和前面的复杂度一样，但是由于最高位为1，所以导致之前 2n 个配对和之后 2n 个配对构成新的逆序关系，即增加了 2n 个逆序数
递推关系：
if(str[0]=='0') DP[0] = 0; else DP[0] = 1; for(int i=1;i<len;i++) { if(str[i]=='0') DP[i] = 2*DP[i-1]%mod; else DP[i] = (2*DP[i-1]%mod + PowerMod(2, 2*i, mod))%mod; } AC代码： /************************************************************************* > File Name: test.cpp > Author: Akira > Mail: qaq.febr2.qaq@gmail.com ************************************************************************/ #include<bits/stdc++.h> typedef long long LL; typedef unsigned long long ULL; typedef long double LD; #define MST(a,b) memset(a,b,sizeof(a)) #define CLR(a) MST(a,0) #define Sqr(a) ((a)*(a)) using namespace std; #define MaxN 100001 #define MaxM MaxN*10 #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 const int mod = 1E9+7; const double eps = 1e-6; #define bug cout<<88888888<<endl; #define debug(x) cout << #x" = " << x << endl; string str; int DP[110]; LL PowerMod(LL a, LL b, LL c) { int ans = 1; a = a % c; while(b>0) { if(b % 2 == 1) ans = (ans * a) % c; b = b/2; a = (a * a) % c; } return ans; } int main() { //std::ios::sync_with_stdio(false); while(cin >> str) { std::reverse(str.begin(), str.end()); CLR(DP); int len = str.length(); if(str[0]=='0') DP[0] = 0; else DP[0] = 1; for(int i=1;i<len;i++) { if(str[i]=='0') DP[i] = 2*DP[i-1]%mod; else DP[i] = (2*DP[i-1]%mod + PowerMod(4, i, mod))%mod; } printf("%d\n", DP[len-1]%mod); //for(int i=len-1;i>=0;i--) cout << DP[i] << endl; } //system("pause"); }