problem1

这个可以贪心地从前向后构造。假设当前已经的字符串为$S$，对于一个字符$c$来说，设将$c$加到$S$后得到的新串为$S^{'}$。那么如果$X+Y+Z \ge minInv$，那么这个之后的构造就是有解的。其中$X$表示$S^{'}$中逆序对个数；$Y$表示剩下的字符与$S^{'}$中的字符构成的逆序对的个数；$Z$表示剩下的字符能构成的最大逆序对个数（从大到小排列即可）。

problem2

首先处理掉垂直发射的情况。剩下的就是不垂直的。直接枚举直线的斜率，即$(x, y)$且$x,y$ 互质。由于斜率为正以及为负是对称的，所以只考虑为正的情况。对于指定的斜率，一共可以画出$L+1$条线。这些线分为两部分，第一部分从矩形的上边出去；第二部分从矩形的右侧出去。对于第一部分，直线经过的格点的数目是确定的，所以只要统计有多少条即可。

对于第二部分，起点越靠后，经过的格点数越少，它的规律是每$x$个经过的格点减少1.即假设从$(t,0)$出发的直线且从右侧出去时经过的格点是$p$，那么从$(t+x,0)$出发的直线经过的格点一定是$p-1$.假设$L=20,H=14,x=3,y=1$,那么从$(0,0),(1,0),(2,0)$出发的直线经过7个格点，从$(3,0),(4,0),(5,0)$出发的直线经过6个，依次类推，所以答案为$x*\sum_{i=K}^{7}C_{i}^{K}=x*\sum_{i=1}^{7}C_{i}^{K}=x*C_{8}^{K+1}$

problem3

每个数字最多有20位，所以只需要考虑20位即可。

对于某一位来说，如果所有数字在这个位上全是1或者全是0，那么不需要考虑这一位。那么现在只需要考虑那么既有0又有1的位。一个分配的原则就是在某一位上所有为0的数字不能分配到一个颜色。

考虑容斥原理。所有的情况有$2^n$种。减去在某一位上出现冲突而在其他位任意的情况（即这一位的所有的0都染成同一个颜色），这时候两个位同时冲突的情况就会多减了一次，所以再加上同时在两位上有冲突而其他位任意的情况。依次类推下去。

 

code for problem1

#include 
     
      #include 
      
       using namespace std;class StrIIRec { public:  string recovstr(int n, int minInv, string minStr) {    if (n == 1) {      return minStr;    }    while (static_cast
       
        (minStr.size()) < n) {      minStr += 'a';    }    std::string s = "";    bool equal = true;    int mask = (1 << n) - 1;    int num = 0;    for (int i = 0; i < n; ++i) {      bool find_it = false;      for (int j = 0; j < n; ++j) {        char c = 'a' + j;        if ((mask & (1 << j)) != 0 && (!equal || c >= minStr[i])) {          int num0 = num;          int remain_max_inv = GetMaxInv(mask ^ (1 << j), n);          for (int k = 0; k < i; ++k) {            if (s[k] > c) {              ++num0;            }          }          if (num0 + remain_max_inv >= minInv) {            s += c;            num = num0;            if (c > minStr[i]) {              equal = false;            }            find_it = true;            mask ^= 1 << j;            break;          }        }      }      if (!find_it) {        return "";      }    }    return s;  }  int GetMaxInv(int remain_mask, int n) {    int result = 0;    int pre = 0;    for (int i = n - 1; i >= 0; --i) {      if ((remain_mask & (1 << i)) != 0) {        result += pre;      } else {        ++pre;      }    }    result += (n - pre) * (n - pre - 1) / 2;    return result;  }};
       
      
     

code for problem2

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          class Spacetsk {  static const int64_t mod = 1000000007; public:  int countsets(int L, int H, int K) {    Init(std::max(L, H) + 1);    int64_t r = Binomial(H + 1, K) * (L + 1) % mod;    if (K == 1) {      return static_cast
          
           (r); } for (int x = 1; x <= L; ++x) { for (int y = H; y >= 1; --y) { if (Gcd(x, y) != 1) { continue; } r += (Compute1(L, H, K, x, y) + Compute2(L, H, K, x, y)) << 1; r %= mod; } } return static_cast
           
            (r); } private: int64_t Compute1(int L, int H, int K, int x, int y) { int x_right; if (H % y == 0) { x_right = L - H / y * x; } else { x_right = L - H * x / y - 1; } if (x_right < 0) { return 0; } int c = x_right + 1; int num = H / y + 1; return Binomial(num, K) * static_cast
            
             (c) % mod; } int64_t Compute2(int L, int H, int K, int x, int y) { int x_right; if (H % y == 0) { x_right = L - H / y * x; } else { x_right = L - H * x / y - 1; } ++x_right; if (x_right < 0) { x_right = 0; } int64_t r = 0; int64_t length = L - x_right; if ((length + 1) % x != 0) { int num = length / x + 1; int c = length % x + 1; r += Binomial(num, K) * static_cast
             
              (c) % mod; length -= c; } int max_num = length / x + 1; r += Binomial(max_num + 1, K + 1) * static_cast
              
               (x); r %= mod; return r; } int64_t Gcd(int64_t x, int64_t y) { return y == 0 ? x : Gcd(y, x % y); } int64_t Binomial(int a, int b) { if (a < b) { return 0; } if (a == 0 || a == b) { return 1; } return p[a] * q[b] % mod * q[a - b] % mod; } void Init(int n) { p.resize(n + 2); q.resize(n + 2); p[0] = q[0] = 1; for (int64_t i = 1; i < p.size(); ++i) { p[i] = p[i - 1] * static_cast
               
                (i) % mod; q[i] = Pow(p[i], mod - 2); } } int64_t Pow(int64_t a, int64_t b) { int64_t r = 1; while (b > 0) { if ((b & 1) == 1) { r = r * a % mod; } a = a * a % mod; b >>= 1; } return r; } std::vector
                
                  p; std::vector
                 
                   q;};
                 
                
               
              
             
            
           
          
         
        
       
      
     

code for problem3

#include 
     
      #include 
      
       using namespace std;class SetAndSet { public:  long long countandset(vector
       
         A) {    long long all = 0;    for (size_t i = 0; i < A.size(); ++i) {      all &= A[i];    }    for (size_t i = 0; i < A.size(); ++i) {      A[i] ^= all;    }    std::vector
        
         
          > v(20, std::vector
          
           ()); for (int i = 0; i < 20; ++i) { for (size_t j = 0; j < A.size(); ++j) { if ((A[j] & (1 << i)) == 0) { v[i].push_back(static_cast
           
            (j)); } } } std::vector
            
              f(A.size()); for (size_t i = 0; i < f.size(); ++i) { f[i] = i; } return dfs(0, f, 1ll, v, A); } long long dfs(size_t dep, const std::vector
             
               &f, long long sgn, const std::vector
              
               
                > &v, const std::vector
                
                  &A) { if (dep == v.size()) { int tot = 0; for (size_t i = 0; i < f.size(); ++i) { if (f[i] == static_cast
                 
                  (i)) { ++tot; } } return (1ll << tot) * sgn; } long long result = dfs(dep + 1, f, sgn, v, A); if (!v[dep].empty()) { static std::vector
                  
                    h(50, 0); static int index = 0; std::vector
                   
                     f_bak = f; ++index; for (size_t i = 0; i < v[dep].size(); ++i) { h[f[v[dep][i]]] = index; } int root = f_bak[v[dep][0]]; for (size_t i = 0; i < A.size(); ++i) { if (h[f_bak[i]] == index) { f_bak[i] = root; } } result += dfs(dep + 1, f_bak, -sgn, v, A); } return result; }};