Codeforces Round 940 (Div. 2) and CodeCraft-23
前四题难度适中，总体还算不错，我想想都能做。E题考察威尔逊和质数筛前缀和算贡献。F题是数据结构，据说很版，还没补。
A题：题意：给出n个木棍，最多组成多少个多边形
Solution：统计各长度木棍的数量，全部贪心成三角形
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
map<int,int>mp;
for(int i=1;i<=n;i++)mp[a[i]]++;
int ans=0;
for(auto [x,y]:mp)ans+=y/3;
cout<<ans<<endl;
}
B:题意：给出n和k，要求把k拆成n个非负整数，希望最大化n个数的或和的二进制的1的数量
Solution:对于n=1进行特判，无法拆分。从一般情况考虑我们只需要找到k的最高的二进制的位的数tmp=(1<<__lg(k))-1,和k-tmp,剩下的数全部为0.考虑这种情况的代价是把最高位的1消耗去获得低位所有的1.
上述贪心显然存在反例就是舒适就是二进制全1的，那么我们考虑特判这类数即可。代码实现过程中直接对两种构造的答案取max，谁大就用谁的构造方案
int cal(int x){
int res=__builtin_popcount(x);
return res;
}
void solve(){
int k;cin>>n>>k;
if(n==1){
cout<<k<<endl;
return ;
}
int len=__lg(k);
int ans=cal(k);
int tmp=(1<<len)-1;
if(ans>=cal(tmp)){
cout<<k<<" ";
for(int i=1;i<=n-1;i++)cout<<0<<" ";
}
else {
cout<<tmp<<" "<<k-tmp<<" ";
for(int i=1;i<=n-2;i++)cout<<0<<" ";
}
cout<<endl;
}
C：题意：人和电脑在正方形网格图里下国际象棋。人每次放白车，人放（x,y)，电脑放黑车(y,x).如果人放对角线，电脑不回应，人继续先手。一个车所在一行一列不能出现第二个车。
现在棋盘大小，给出前k步棋谱，求最终局面有多少种局面
Solution:考虑给出递推的证明。首先注意到问题只和当前还有几行几列空闲有关，已经被占领的行无法对方案做出贡献。考虑现在填一个n行n列的空白棋盘。由于顺序与最终方案无关，所以根据任意性，我们假设考虑第一步就在第n行落子，也就是说第n行的落子可能是在第j步，当前钦定第一步放，就去除了重复局面 对计算造成的影响。
\(dp[n]=dp[n-1]+2*(n-1)*dp[n-2]\).含义是如果落子在第n行的对角线则问题划归到n-1规模，如果落子在第n行非对角线，则电脑对应位置落黑车，会减少两行两列，问题划归到n-2规模.考虑可以在第n列对称，方案数直接*2.
int dp[N];
void solve(){
//cout<<dp[3]<<endl;
int k;
cin>>n>>k;
for(int i=1;i<=k;i++){
int x,y;cin>>x>>y;
if(x==y)n-=1;
else n-=2;
}
cout<<dp[n]<<endl;
}
D题意：\(\left(\bigoplus_{x\le i\le z} a_i \right)\oplus a_y > \left(\bigoplus_{x\le i\le z} a_i \right)\)，求满足条件的x，y，z有多少对，其中\(x<=y<=z\)
首先套路的，对于区间异或和提前预处理前缀异或和，考虑不等式成立条件，从\(a_{y}\)的二进制最高位考虑，当对应区间异或和该位为0的时候不等式成立。为0的条件的区间异或和两个端点需要同时为1或者为0.
所以我们可以预处理拆位的前缀和，后缀和，每次统计的是1的数量，0的数量作为补集也很好得到。
onst int len=__lg((ull)2e9);
bitset<5>b;
//a_{y}^t>t 考虑a_{y}的最高位，如果t这位为0，那么不等式成立。
//如果t这位为1，不等式一定不成立
//考虑枚举y，然后看他左边和右边的这一位的前缀和有多少异或结果为0
//拆位前缀和，后缀和，快速统计数量
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>s(n+1,0);
for(int i=1;i<=n;i++)s[i]=s[i-1]^a[i];
vector<vector<int>>pre(n+2,vector<int>(len+2,0));
vector<vector<int>>suf(n+2,vector<int>(len+2,0));
for(int i=1;i<=n;i++){
for(int j=len;j>=0;j--){
int u=(s[i]>>j)&1;
if(u==1)pre[i][j]=1;
}
}
for(int i=n;i>=1;i--){
for(int j=0;j<=len;j++){
suf[i][j]=suf[i+1][j]+pre[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=len;j++){
pre[i][j]+=pre[i-1][j];
}
}
int ans=0;
// for(int i=1;i<=n;i++){
// b=s[i];
// cerr<<b<<endl;
// }
for(int i=1;i<=n;i++){
int u=__lg(a[i]);
int c1=pre[i-1][u];
int c2=suf[i][u];
// cerr<<u<<" "<<c1<<" "<<c2<<endl;
ans+=c1*c2;
//考虑这里0也可以作为本位为0贡献
ans+=(max(i-c1,0LL))*(max(n-i+1-c2,0LL));
}
cout<<ans<<endl;
}
E:定义一种F运算，求\(\sum\limits_{i=1}^n \sum\limits_{j=1}^i \left( F(i,j) \bmod j \right).\)给出\(F(i,j)\)的定义是从i个元素中选j个元素进行圆排列的方案数。显然\(F(i,j)=C(i,j)*(j-1)!\)
Solution：我们需要进一步变形上面式子\(F(i,j) \bmod j = \frac{i(i-1)\cdots(i-j+1)}{j} \bmod j = \left( (j-1)! \times \left\lfloor \frac{i}{j} \right\rfloor \right) \bmod j\)
考虑对将组合数拆成阶乘，然后发现分子连续j项一定构成modj的剩余系，所以可以进一步化简成下取整形式。
- 考虑威尔逊定理，对于所有质数\((j-1)! \equiv -1 \bmod j\)
- 对于所有大于4的合数，\((j-1)! \equiv 0 \bmod j\)
因此我们需要计算对于固定质数j，不同的i对其的贡献，这里就是交换了求和次序。
对于固定j，不同的i造成的贡献如何快速计算？
一般地，对于i从kp到k(p+1)-1，他们的贡献是相同的，我们希望这段i每个数都加上-k modj的贡献，静态区间加我们使用差分维护贡献。最后我们求一遍前缀和得到每个i的贡献，再求一遍得到前n个数的贡献，也就是答案了
我们还需要对4进行单独计算，作为特例。
int minp[N];
int prime[N];
int cnt=0;
int ans[N];
int g[N];
//打表固然美丽，但数学推导更为重要，推出数学式子才理解他们说的打表规律的本质
//题解写的很不错
//总的来说就是先推数学式子用威尔训化解，对于4特判。
//对于所有质数算贡献，交换求和次序，统计答案差分后，前缀和求出所有答案
void init(){
for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间
int cnt = 0;
for (int i = 2; i < N; i++) {
if (minp[i] == i) prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j] * i < N; j++) {
minp[prime[j] * i] = prime[j];
if (i % prime[j] == 0) break;
}
}
for(int i=0;i<cnt;i++){
int p=prime[i];
// if(p<300)cerr<<p<<endl;
for(int j=p;j<=1000000;j+=p){
int u=-j/p;u=(u%p+p)%p;
// int u = (p - ((j / p) % p)) % p;
// if(j<100)cerr<<p<<" "<<u<<endl;
g[j]+=u;g[j]%=mod;
if(j+p<N){g[j+p]-=u;g[j+p]+=mod;g[j+p]%=mod;}
}
}
int p=4;
for (int j=4;j<=1000000;j+=4){
int u=2*j/p;u%=p;
g[j]+=u;g[j]%=mod;
if(j+p<N){g[j+p]-=u;g[j+p]+=mod;g[j+p]%=mod;}
}
for(int i=1;i<=1000000;i++){
g[i]+=g[i-1];g[i]%=mod;
ans[i]=ans[i-1]+g[i];ans[i]%=mod;
}
}