1、给定长度为$n$ 的数组$b$，构造长度为$n$ 的且没有重复元素的数组$a$，令$p_{i}$表示$a$中除$a_{i}$外其他元素的乘积。构造出的$a$满足$a_{i}^{b_{i}}$能够被$p_{i}$整除。这样的数组$a$存在否？

思路：因为$a_{i}^{b_{i}}$中所有素因子的指数大于等于$p_{i}$。所以可以假设所有的$a_{i}$只含有素因子2。令$a_{i}=2^{A_{i}},s=\sum_{i=1}^{n}A_{i}$，那么有$A_{i}b_{i}\geq s-A_{i}$，即$A_{i}\geq \frac{s}{1+b_{i}}$。所有这些加起来约去$s$得到$\sum_{i=1}^{n}\frac{1}{1+b_{i}}\leq 1$。令$K=\sum_{i=1}^{n}\frac{1}{1+b_{i}}$。所以$K>1$无解。$K=1$但是存在相同的$b$时无解。因为$K=1$说明$A_{i}= \frac{s}{1+b_{i}}$，但是相同的$b$ 导致出现了相同的$A$。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;class DivisibleSetDiv1{public: string isPossible(vector 
            
              b) { const int n=(int)b.size(); sort(b.begin(),b.end()); double ans=0; for(int i=0;i
             
              1+1e-10) { return "Impossible"; } else if(ans>1-1e-10) { for(int i=1;i
             
            
           
          
         
        
       
      
     

　　

2、有$n$匹马，每个马有个各不相同的值$a_{i}$。有$2^{m}$场比赛。第$i$匹马在第$j$场比赛中的用时为$a_{i}$^$j$（抑或）。每场比赛所有的马排名为$[0,n-1]$。排名为$k$的马得到的罚时为$k^{2}$。所有比赛结束后每匹马的所有罚时加起来得到第$i$匹马的总罚时$p_{i}$，计算所有$p_{i}$%1000000007的抑或值。

思路：将每匹马的值$a_{i}$建立一课二叉树，并在节点上记录子树中插入的马的个数。然后依次计算每一匹马的$p_{i}$值。对于第$i$匹马，设比赛$j$的二进制高$t$位等于$a_{i}$的高$t$位的所有比赛中它的罚时为$g=\sum_{r=1}^{2^{m-t}}s_{r}^{2}$。$2^{m-t}$是因为已经进行了这么多长比赛。那么在进行比赛的二进制第$m-t$位不同于$a_{i}$的第$m-t$位但是它们的高$t-1$ 位相同时的所有比赛中，它的罚时为$g^{'}=\sum_{r=1}^{2^{m-t}}(s_{r}+x)^{2}$。其中$x$为与$a_{i}$ 的第$m-t$位不同的一侧所有马的个数。那么$g^{'}=g+2^{m-t}x^{2}+2x\sum_{r=1}^{2^{m-t}}s_{r}$。这样记录已经遍历的子树的前缀和$\sum_{r=1}^{2^{m-t}}s_{r}$即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int N=200005;const int mod=1000000007;int a[N];int T[N*32][2];int S[N*32];int e;int m;void add(int x){ int p=1; for(int i=m-1;i>=0;--i) { int t=(x>>i)&1; if(!T[p][t]) T[p][t]=++e; p=T[p][t]; ++S[p]; }}int c[32];void cal(int x){ int p=1; for(int i=m-1;i>=0;--i) { int t=(x>>i)&1; c[i]=S[T[p][t^1]]; p=T[p][t]; }}class XorOrderDiv1{public: int get(int M,int n,int a0,int b) { m=M; a[1]=a0; for(int i=2;i<=n;++i) a[i]=(a[i-1]+b)&((1<