20220912--CSP-S模拟4

A. 石子游戏

首先了解一个叫做 \(\operatorname{Nim}\) 游戏的玩意
通常的 \(\operatorname{Nim}\) 游戏的定义是这样的：
有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”
如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）
那么有一个美妙的结论：如果石子数的异或和为 \(0\) 则后手必胜，否则先手必胜
证明：如果石子数的异或和为 \(0\) ，也即 \(a_1\oplus a_2 \oplus \cdots \oplus a_n=0\)
那么改变一个数字 \(a_i\) 使原式异或和不为 \(0\) ，设改变后的二进制表示为 \(\Delta_2\)
那么一定存在某个 \(a_j\) 在 \(\Delta_2\) 的最高位上是 \(1\)（否则无法得到这个 \(1\) ）
改变这个 \(a_j\) 即可
对于本题只要将所有 \(a_i\) 模 \(x+1\) 求异或和是否为 \(0\)

关于数组 \(f\) ：
题解里面预处理的 \(f\) 数组是基于位运算的，\(f[i][j]\) 是由第 \(j+1\) 位加一个 \(1\)转移过来的，
然后这一段区间使用了状压的思想枚举了子集算出的和累加的贡献
把后面的式子拆开就可以发现，累加的次数刚好为 \([0,2^j−1]\)
这还表明了一个问题，就是只有偶数段才会做贡献。别着急问偶数段是啥，先听我说
刚才说累加的次数只有 \(2^j\) 次，而 \(2^{j+1}=2^j\times 2\)是累加次数的二倍
再看累加的起点终点，不难发现，如果把 \(2^j\) 长度称为一段，那么 \(2^{j+1}\) 就是两段，分开考虑这两段。
因为累加的起点在第二段开头也就是 \(i+2^j\) 而不是 \(i\)
所以每次加上一个 \(2^j+1\)长度的区间里面都只有第二段做出了累加的贡献，所以说只有偶数段才做贡献。
关于答案计算：
对于枚举每一个 \(x+1\) ，我们枚举一个 \(j\)， 显然只会枚举到 \(\log_2(x)\)
然后我们再枚举一下可能的 \(k\) 找到一段要计算的区间 \([l,r]\) ，使用向下取整的方式找到距离 \(r\) 最近的 \(l+2^{j+1}\)
这一段的贡献可以用预处理出的数组直接做后缀和求出
然后考虑区间 \([l+2^{j+1},r]\) ，这段区间如果是在奇数区间，则不用计算单独的贡献，因为他没有
如果有一些在偶数区间或者被偶数区间包含，就需要使用前缀和求出贡献，很好求，直接最右端减去最左端就行
算出的这个数如果是奇数，就会有贡献，给计数器上的 \(j\) 位异或一个 \(1\)
因为要计算总和，现在枚举的是区间，需要找的是所有可能区间的答案的和是否为奇数
所以是异或，不是与，如果两个区间都是奇数那答案就会变成偶数。
这样就差不多了。

点击查看代码

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=501000,INF=1099588621776;
int n,cnt[WR<<1];
int dp[WR<<1][55];
int read(){int s=0,w=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}return s*w;
}
signed main(){freopen("stone.in","r",stdin);freopen("stone.out","w",stdout);n=read();for(int i=1;i<=n;i++) cnt[read()]++;for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];for(int i=n;i!=-1;i--)for(int j=0;j<=log2(n-i+1);j++)dp[i][j]=dp[min(i+(1<<(j+1)),n)][j]+cnt[min(i+(1<<(j+1))-1,n)]-cnt[i+(1<<j)-1];for(int y=2;y<=n+1;y++){int tmp=0;bool flag=0;for(int j=0;j<=log2(y-1);j++){for(int k=0;k*y<=n;k++){int l=k*y,r=min((k+1)*y-1,n),flr=(r-l+1)>>(j+1);bool lim=(l+flr*(1<<(j+1))+(1<<j)<=r);if((dp[l][j]-dp[l+flr*(1<<(j+1))][j]+lim*(cnt[r]-cnt[l+flr*(1<<(j+1))+(1<<j)-1]))&1) tmp^=1<<j;}if(tmp){flag=1;break;}}printf(flag?"Alice ":"Bob ");}fclose(stdin);fclose(stdout);return 0;
}

C. 黑客

首先如果你像我一样上来先一眼线性筛了 \(\mu\) 函数准备莫反那么恭喜你
你假了
咳，正经的做法非常显然
对于一组数据 \([a,b],[c,d]\)
针对每一个分数，设为 \(\frac{p}{q}\)
我们都可以找到 \(l_1,r_1,l_2,r_2\) 使得 \(l_1p>=a\; ,\; r_1p<=b\) 且 \(l_2q>=c\; ,\; r_2q<=d\)
那么分数可以变成 \(\frac{\lambda p}{\mu q}\) ，\(\lambda \in [l_1,r_1]\; ,\; \mu\in [l_2,r_2]\)
显然地，当 \(\lambda=\mu\) 的时候可以约分，这样的 \((\lambda,\mu)\) 共有 \(\min(r_1,r_2)-\max(l_1,l_2)+1\) 组

点击查看代码

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=501000,INF=1099588621776,mod=1e9+7;
int a,b,c,d;
int ans;
int read(){int s=0,w=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}return s*w;
}
int gcd(int a,int b){if(!b) return a;return gcd(b,a%b);
}
signed main(){freopen("hacker.in","r",stdin);freopen("hacker.out","w",stdout);a=read(),b=read(),c=read(),d=read();for(int i=1;i<=998;i++){for(int j=1;j<=999-i;j++){if(gcd(i,j)!=1) continue;int l=max((int)ceil((double)a/i),(int)ceil((double)c/j));int r=min((int)floor((double)b/i),(int)floor((double)d/j));// printf("%lld %lld\n",l,r);if(r>=l) ans=(ans+(i+j)*(r-l+1)%mod)%mod;}}printf("%lld\n",ans);fclose(stdin);fclose(stdout);return 0;
}

D. 黑客（续）

无耻的高精度题
无耻的卡常题
不是这么做真的有任何必要吗？？？
考虑一个数位 \(\operatorname{DP}\)
设当前数字选择状态为 \(S\) ，当前递归到了第 \(pos\) 位
然后非常显然地就可以写出代码

这个只有90分

//RNM高精度!!!!!!退钱!!!!!!!
#include<cstdio>
#include<cstring>
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=510,INF=1099588621776,mod=1e17;
struct BigNum{int num[70],len;void clr(){memset(num,0,sizeof(num));len=0;}BigNum operator =(int val){clr();while(val){num[++len]=val%mod;val/=mod;}return *this;}BigNum operator +(const BigNum &b)const{BigNum res=*this;for(int i=1;i<=b.len;i++){res.num[i]+=b.num[i];res.num[i+1]+=res.num[i]/mod;res.num[i]%=mod;}while(res.num[++res.len]){res.num[res.len+1]+=res.num[res.len]/mod;res.num[res.len]%=mod;}while(res.len>1&&!res.num[res.len]) res.len--;return res;}BigNum operator +=(const BigNum &b){*this=*this+b;return *this;}BigNum operator *(const int &b)const{BigNum res=*this;for(int i=1;i<=res.len;i++) res.num[i]*=b;for(int i=1;i<=res.len;i++){res.num[i+1]+=res.num[i]/mod;res.num[i]%=mod;}while(res.num[++res.len]){res.num[res.len+1]+=res.num[res.len]/mod;res.num[res.len]%=mod;}while(res.len>1&&!res.num[res.len]) res.len--;return res;}BigNum operator *=(const int &b){*this=*this*b;return *this;}void print(){printf("%lld",num[len]);for(int i=len-1;i>=1;i--){if(!len) break;printf("%017lld",num[i]);}printf("\n");}
};
int n,m,k;
int ban[WR];
pair<BigNum,BigNum>dp[WR][(1<<9)+10];
int read(){int s=0,w=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}return s*w;
}
pair<BigNum,BigNum> dfs(int pos,int S){if(dp[pos][S].first.num[1]>=0) return dp[pos][S];if(pos>n){BigNum tmp1,tmp2;tmp1=1,tmp2=0;return dp[pos][S]=make_pair(tmp1,tmp2);}dp[pos][S].first=0;for(int i=1;i<=k;i++){if(!(S&ban[i])){pair<BigNum,BigNum>res=dfs(pos+1,S|(1<<(i-1)));dp[pos][S].first+=res.first;res.first=res.first*i,res.second=res.second*10;dp[pos][S].second=dp[pos][S].second+res.first+res.second;}}return dp[pos][S];
}
signed main(){freopen("hacker2.in","r",stdin);freopen("hacker2.out","w",stdout);n=read(),m=read(),k=read();int tmp=(1<<k);for(int i=1;i<=n+1;i++){for(int j=0;j<tmp;j++){dp[i][j].first=-1;}}for(int i=1;i<=m;i++){int a=read(),b=read();ban[a]|=(1<<(b-1));}pair<BigNum,BigNum>ans;ans=dfs(1,0);ans.first.print();ans.second.print();fclose(stdin);fclose(stdout);return 0;
}

又强又可爱的Eafoo的AC

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <cassert>
%:pragma GCC optimize(3)
using namespace std;typedef long long ll;int read() {int x = 0;char c;bool f = 0;while (!isdigit(c = getchar())) {if (c == '-') f = 1;}do {x = (x << 1) + (x << 3) + (c ^ 48);} while (isdigit(c = getchar()));if (f) return -x;return x;
}const int maxn = 5e2 + 1, maxs = (1 << 9);struct Int {ll num[80];Int() { num[0] = 1; }const ll len = 1e17;void Init() { memset(num, 0, sizeof num); num[0] = 1; }Int operator +(const Int &b) const {Int c;c.Init();c.num[0] = max(num[0], b.num[0]);for (int i = 1; i <= c.num[0]; ++i) {c.num[i] += num[i] + b.num[i];if (c.num[i] >= len) {c.num[i] -= len;++c.num[i + 1];}}if (c.num[c.num[0] + 1] > 0) ++c.num[0];return c;}Int operator *(int b) const {Int c; c.Init();c.num[0] = num[0] + 1;for (int i = 1; i <= c.num[0]; ++i) {c.num[i] += num[i] * b;c.num[i + 1] += c.num[i] / len;c.num[i] %= len;}while (c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];return c;}void operator +=(const Int &b) {num[0] = max(num[0], b.num[0]);for (int i = 1; i <= num[0]; ++i) {num[i] += b.num[i];if (num[i] >= len) {num[i] -= len;++num[i + 1];}}if (num[num[0] + 1] > 0) ++num[0];}void operator *=(int b) {++num[0];for (int i = 1; i <= num[0]; ++i) {num[i] += num[i] * (b - 1);num[i + 1] += num[i] / len;num[i] %= len;}while (num[num[0]] == 0 && num[0] > 1) --num[0];}void put() {printf("%lld", num[num[0]]);for (int i = num[0] - 1; i; --i) printf("%017lld", num[i]);}void putln() { put(), putchar('\n'); }
};bool ok[maxs][10];
Int f[2][maxs];
Int sum[2][maxs];
bool ban[10][10];signed main() {#ifndef DEBUGfreopen("hacker2.in", "r", stdin);freopen("hacker2.out", "w", stdout);#endifint n = read(), m = read(), p = read();for (int i = 1; i <= m; ++i) {int a = read(), b = read();ban[b][a] = 1; // b前 没有 a}int Max = 1 << p;for (int i = 0; i < Max; ++i) {for (int j = 1; j <= p; ++j) {bool f = 0;for (int k = 1; k <= p; ++k) {if (!((i >> (k - 1)) & 1)) continue;if (ban[j][k]) { f = 1; break; }}if (!f) ok[i][j] = 1;}}int pi = 0;f[pi][0].num[1] = 1;for (int i = 1; i <= n; ++i) {pi ^= 1;for (int j = 0; j < Max; ++j) f[pi][j].Init(), sum[pi][j].Init();for (int j = 0; j < Max; ++j) {for (int k = 1; k <= p; ++k) {if (!ok[j][k]) continue;int s = j | (1 << (k - 1));f[pi][s] += f[pi ^ 1][j];sum[pi][s] += sum[pi ^ 1][j] * 10;sum[pi][s] += f[pi ^ 1][j] * k;}}}Int ans, ans1;ans.Init(), ans1.Init();for (int i = 0; i < Max; ++i) ans += f[pi][i], ans1 += sum[pi][i];ans.putln();ans1.putln();
}