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 <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
class DivisibleSetDiv1
{
public:
string isPossible(vector <int> b)
{
const int n=(int)b.size();
sort(b.begin(),b.end());
double ans=0;
for(int i=0;i<n;++i) ans+=1.0/(b[i]+1);
if(ans>1+1e-10) {
return "Impossible";
}
else if(ans>1-1e-10) {
for(int i=1;i<n;++i) if(b[i]==b[i-1]) {
return "Impossible";
}
}
return "Possible";
}
};
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}+2xsum_{r=1}^{2^{m-t}}s_{r}$。这样记录已经遍历的子树的前缀和$sum_{r=1}^{2^{m-t}}s_{r}$即可。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
#include <assert.h>
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<<m)-1);
e=1;
for(int i=1;i<=n;++i) add(a[i]);
int ans=0;
for(int i=1;i<=n;++i)
{
cal(a[i]);
int tmp=0,sum=0;
for(int j=0;j<m;++j)
{
tmp=(tmp+(long long)(1<<j)*c[j]%mod*c[j]%mod+(long long)2*c[j]%mod*sum%mod+tmp)%mod;
sum=(sum*2+(long long)c[j]*(1<<j))%mod;
}
ans^=tmp;
}
return ans;
}
};