2023-09-07 14:35:48 部分是洛谷题解
A
不难想到我们要先记录一下每一位的前缀 \(\gcd\)，我们发现我们选择一位的前缀 \(\gcd\) 除掉以后，前缀 \(\gcd\) 会变为 \(1\) 并且会导致这位之后的 \(\gcd\) 全部为 \(1\)。所以每一位只能选择一次，并且我们从后往前扫肯定比从前往后扫要更优。
我们先把原序列原答案算出来，然后判断每一次除当前位的 \(\gcd\) 是否对答案有正贡献，贪心选择。这样为什么对呢？考虑我们第 \(i\) 位的贡献为正，但是我们不选，到 \(i-1\) 的时候，贡献可能变大，那显然我们后面除了对前面也没有影响，前面依然可以除剩下的，但是如果变小，说明前面不用除要让后面除。所以我们贪心从后往前选择是更优的。
如果我们直接贪心选了以后把前面的 \(\gcd\) 都除掉，发现复杂度是 \(O(n^2\sqrt{a})\) 的，这样肯定不行。注意到我们 \(\gcd\) 是单调不增的，所以我们从后往前是单调不减的，记录一下即可做到 \(O(n\sqrt{a})\)，然而用线性筛跑了之后是远远跑不满的。
\(Code\)
int n,m,tot,prime[100005];
bool vis[100005];
ll ans,a[5002],b[5002];
unordered_set<ll>pd;
void init(){
for(int i=2;i<=100000;i++){
if(!vis[i])prime[++tot]=i;
for(int j=1;j<=tot&&prime[j]*i<=100000;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
ll cal(ll x){
ll res=0;
for(int i=1;prime[i]*prime[i]<=x;i++){
if(x%prime[i])continue;
ll cnt=0;
while(x%prime[i]==0)x/=prime[i],cnt++;
if(pd.find(prime[i])!=pd.end())res-=cnt;
else res+=cnt;
}
if(x>1){
if(pd.find(x)!=pd.end())res--;
else res++;
}
return res;
}
int main(){
n=read(),m=read();
init();
for(int i=1;i<=n;i++){
a[i]=read();
if(i==1)b[i]=a[i];
else b[i]=__gcd(b[i-1],a[i]);
}
for(int i=1;i<=m;i++)pd.insert(read());
for(int i=1;i<=n;i++)ans+=cal(a[i]);
for(ll i=n,used=1,o;i;--i)
if((b[i]/used>1)&&(o=cal(b[i]/used))<0)ans-=o*i,used=b[i];
cout<<ans;
return 0;
}
B
题意
制作一件物品需要经过两次加工，负责第一次加工的有 \(n\) 台机器，每台机器加工时间为 \(a_i\)；负责第二次加工的有 \(m\) 台机器，每台机器加工的时间为 \(b_i\)，所有的机器同一时间只能加工一件物品。现在有 \(l\) 个原材料，每个原材料必须先经过第一次加工才能进行第二次加工，假设花费的时间只有在机器上加工的时间，问你最少要花费多少时间才能加工完全部的物品，即最后一件物品加工出来的最小时间。
思路
被 T3 耗了太长时间，先想想怎么拿部分分。
当 \(l=1\) 的时候，显然是选加工时间最少的两台机器最优。
当 \(l,n,m\le 10\) 的时候，可以直接搜索乱搞，比如离散时间后枚举每台机器在哪个位置加工，感觉代码比正解还长就没去打。
当 \(b_i=0\) 时，我们直接二分使得第一次加工最快完成的答案就行了。（如果在这里想到贪心就可以直接想正解了，不需要牛马二分）
30pts \(Code\)
bool check(ll lim,int n,int a[],int to){
ll tot=0;
for(int i=1;i<=n;i++){
if(!a[i])return 1;//不加这句话只有10分。。
tot+=lim/a[i];
if(tot>=to)return 1;
}
return 0;
}
int n,na,nb,a[100005],b[100005];
int main(){
n=read(),na=read(),nb=read();
for(int i=1;i<=na;i++)
a[i]=read();
for(int i=1;i<=nb;i++)
b[i]=read();
sort(a+1,a+1+na),sort(b+1,b+1+nb);
ll l=0,r=1e14,ans=0;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid,na,a,n))r=mid-1;
else l=mid+1;
}
ans=l;
l=0,r=1e14;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid,nb,b,n))r=mid-1;
else l=mid+1;
}
cout<<ans+l;
return 0;
}
正解
正解讲的很抽象，很难理解其正确性。每次加入到同一个机器 \(a_i\) 相当于增加一个机器 \(a_i+t\)，然后将小的 \(a_i\) 和大的 \(b_i\) 配对？还是不能理解正确性。但是这题就是这么过了。
\(Code\)
int n,m,L;
ll a[100005],b[100005],w[100005],ans;
priority_queue<PII,vector<PII>,greater<PII> >q1,q2;
int main(){
L=read(),n=read(),m=read();
for(int i=1;i<=n;i++)q1.push({a[i]=read(),i});
for(int i=1;i<=m;i++)q2.push({b[i]=read(),i});
for(int i=1;i<=L;i++){
ll t=q1.top().first,id=q1.top().second;
q1.pop();
q1.push({t+a[id],id});
w[i]=t;
}
for(int i=L;i;--i){
ll t=q2.top().first,id=q2.top().second;
q2.pop();
q2.push({t+b[id],id});
ans=max(w[i]+t,ans);
}
cout<<ans;
return 0;
}
C
前排提示：和常规思路大相径庭，对多做法感兴趣的同学可以看一下。
题意
给定一个长度为 \(n\)(\(1\le n\le 5\times 10^5\)) 的字符串，请你将其分成 \(k\) 段使得每一段都不存在循环节。
如 bbc 和 ababa 是合法的字符串，而 bbbb 和 abab 不是合法字符串。
求 \(k\) 的最小值以及取到最小值时合法拆分方案数。
思路
一开始想多了（想少了），什么枚举断点（因为除了循环节长度为是 \(1\) 即只有一个字符的情况 \(k=n\)，其他要么是 \(k=1\) 要么 \(k=2\)），虽然枚举断点的做法可以通过 KMP 的失配指针做到 \(O(n)\) 预处理，\(O(1)\) 查询使得最终复杂度为 \(O(n)\)，但是我显然不会高深的 exkmp，所以我就乱打了一个 \(O(n\log ^2 n)\) 的做法，考场上调了两个小时差一点就过了（样例不够，没想到前缀循环节还可以前缀前缀循环节，只减了第一个出现的）。
我们直接判断原串是不是循环串，以及其最小循环节长度。我们从 \([1,n/2]\) 枚举循环节
长度 \(len\)，然后用一个 \(O(\log \dfrac{n}{len})\) 的方法找出循环节重复到长度与原串相同后的哈希值与原串的哈希值比较即可，复杂度 \(O(n\log n)\)。
然后呢？我们先假设我们找到的循环节的前缀和后缀都没有循环串。
那么发现最小循环节长度 \(len\) 满足 \(2<len<\dfrac{n}{2}\) 时，我们只要不从循环节断开就可以使两边都合法，答案为 \(k=2,ans=n-\dfrac{n}{len}\)。
对于循环节长度为 \(1\) 的，答案为 \(k=n,ans=1\)，这个很显然，只有分成每个字母一段才能保证其没有循环节对吧。
对于循环节长度为 \(\dfrac{n}{2}\) 的，因为此时中间可以拆开，剩下的虽然是原来的循环节但是其本身不是循环串，所以答案为 \(k=2,ans=n-1\)。
如果没有循环节，也就是本来就合法，那答案就是 \(k=1,ans=1\) 了。
有人可能会问，为什么除了两个特殊情况外，\(k\) 都可以为 \(2\) 呢？很显然，因为我们找的是最小循环节，那么最小循环节本身已经合法，因为此时我们只需要分成两个合法串，假设我把一个循环节断开后它能和本身构成一个循环串，那原循环节肯定不是最小循环节。
所以不管这个循环节的前后缀是不是循环节，我们都至少可以从末尾的一个把原串分成 \([1,n-1],[n,n]\)，两部分，上面证明了 \([1,n-1]\) 的部分一定不是循环串，剩下的一个字符不算循环串，那这里至少已经有方案了，所以 \(k=2\)。
我们发现我们这样的做法并不能处理循环节的前缀或者后缀有循环串的情况，比如一个串 bcbccbcbcc，显然我们最小循环节是 bcbcc，但是我们并不能分成 bcbc,cbcbccc，这样前面那串就不合法。因为我们只分成两部分，也就是只有循环节的前缀和后缀可能会导致答案出错。
那怎么办呢？简单啊，我们只需要枚举循环节中所有前缀（和后缀）循环节的长度，然后继续用一个 \(O(\log n)\) 复杂度求循环串哈希的方法算出可能的哈希，然而我们并不知道前缀循环节在原循环节中重复的次数，那怎么办呢？
这时假设我们发现 bcbcbcbcbb 中前缀循环节重复次数可以为 \(3\)，那么重复次数 \(\le 3\) 的显然都可以，满足二分性质，那直接再跑个二分就好了。
考场上止步于此，没有考虑可能有多个得去掉的循环节的情况。
那我们已经找到了所有前缀（后缀）循环节的最大重复次数，如何统计答案使得其不重复呢？有想到说我们发现长度为 \(2\) 的前缀循环节可行，那么 \(2\) 的倍数都给标记掉，虽然但是，这样只能拿 \(94 pts\)，会被卡掉一个点，为什么？因为前缀 ababbcababbc .... 的长度为 \(6\) 的循环节并不是 ababab，没有被 \(2\) 的包含。
所以我们又想到最初的性质，我们假设有一个长度为 \(len\) 的循环节 \(s_1\)，如果它合法，那么它的任意次（大于 \(1\)）重复串一定不是长度 \(<len\) 的任何循环节 \(s_2\) 的重复串的前缀。考虑如果是前缀，因为 \(s_2\) 长度小于 \(len\)，因为 \(s_1\) 显然跟其重复的相同，那么可以得到 \(s_1\) 就是 \(s_2\) 的重复串，不合法。得证。
既然更大的循环节重复串不会是小的的前缀，那么我们只需要判断每次长度是否有增长即可，前缀重复串长度增加，说明其不是小的的前缀，可以加入答案中。举个例子 ababaababa 虽然 ababa 循环节可以被 ab 的重复串包含，但是其重复串没被包含，那么 ab 和 ababa 都能算进答案，因为 abab 是 ababa 的前缀，重复后长度增加。后缀的计算方式同理，倒着跑一遍就好了。
我们可以在计算最小循环节时顺便记录一下每个循环节的最大循环次数，哈希值重复复杂度 \(O(\log n)\)，二分 \(O(\log n)\)，循环复杂度 \(O(n)\)，总复杂度 \(O(n\log ^2 n)\)，看着很大，其实完全跑不满，在学校 OJ 上跑飞快，看上去就像是 \(O(n)\) 常数大一点？
说了这么多，怎么 \(O(\log n)\) 算出循环节重复若干次后的哈希值呢？
前置小技巧：哈希快速幂
这个非常《智慧》的想法是我在考场上想出来为了快速计算循环节字符串的，这个名字也是我瞎取的，见笑了。
假设我们已经有了一个合法字符串，显然我们将其重复多次，它就变成了一个循环字符串。
但是如果我们的要求的字符串长度为 \(n\)，而循环节长度为 \(len\)，那么复杂度就为 \(\dfrac{n}{len}\)，而别忘了我们要从 \([1,n/2]\) 枚举循环节长度，所以显然不能用一些 \(O(n)\) 的方法取一个个算是不是循环节，考虑如何 \(O(\log n)\)。
考虑把原字符串搞成哈希值，每次取出一个循环节，根据长度计算其需要重复的次数，然后用类似于快速幂的思想不断重复即可。
ll hash_qpow(ll x,int v,int w){
ll res=0,len=v;
for(;w;w>>=1,x=x*P[len]+x,len=len*2)
if(w&1)res=res*P[len]+x;
return res;
}
还没听懂的话可以结合代码理解一下。
\(Code\)
typedef unsigned long long ll;
const int p=1331;
ll ha[500005],P[500005];
int pre[500005],sub[500005];
bool vis[500005];
ll hash_qpow(ll x,int v,int w){//哈希快速幂
ll res=0,len=v;
for(;w;w>>=1,x=x*P[len]+x,len=len*2)
if(w&1)res=res*P[len]+x;
return res;
}
bool check(int x,int n,int nb[]){//二分处理最大前缀（后缀）重复次数
int l=1,r=n/x,anss=1;
while(l<=r){
int mid=(l+r)>>1;
ll res=hash_qpow(ha[x],x,mid);
if(res==ha[x*mid])l=mid+1,anss=mid;//如果能对上说明可以重复这么多次
else r=mid-1;
}
nb[x]=anss;//记录
return (n%x==0&&anss==n/x);//如果能重复到 n/len 次，那不就是最小循环节了吗
}
int n;
int main(){
string l;
cin>>l;
n=l.length();
l=" "+l+" ";
P[0]=1;
for(int i=1;i<=n;i++){//计算前缀哈希值
ha[i]=ha[i-1]*p+(l[i]-'a');
P[i]=P[i-1]*p;
}
int len=0;
for(int i=1;!len&&i<=(n>>1);i++)//注意！！找到了就退出，不会有比最小循环节更大的前缀长度了
if(check(i,n,pre))len=i;//处理前缀数组和最小循环节
if(!len)return printf("1\n1"),0;//如果本身就合法
else if(len==1)return printf("%d\n1",n),0;//如果只有一个字符，全分开
puts("2");
int ans;
if(len==n/2)ans=n-1;//先把答案算出来，之后去重
else ans=n-n/len;
reverse(l.begin(),l.end());//倒过来算后缀
for(int i=1;i<=n;i++)
ha[i]=ha[i-1]*p+(l[i]-'a');
len=0;
for(int i=1;!len&&i<=(n>>1);i++)//同样的方法处理后缀
if(check(i,n,sub))len=i;
int lim=0;//最大长度
for(int i=1;i<len;i++){//在大的循环节里面找小的循环节前缀
if(pre[i]*i>lim){//如果可以超越就更新答案
ans-=pre[i]-1;//可以切的只剩下最后一个，所以减1
lim=pre[i]*i;//更新长度
}
}
lim=0;
for(int i=1;i<len;i++){//后缀同理
if(sub[i]*i>lim){
ans-=sub[i]-1;
lim=sub[i]*i;
}
}
printf("%d\n",ans);
return 0;
}
后记
我也不知道为什么想出来了个这么离谱的做法，反正主要是因为想到了这个哈希快速幂就想着一定要用这个思想给它打出来，然后就变得有亿点复杂了？
D
原题：AT_dp_y Grid 2,CF559C Gerald and Giant Chess。
特殊性质版：[ARC058D] いろはちゃんとマス目
思路
盯一眼数据范围，\(H,W\le10^5,n\le 3000\)，那大概就是个 \(O(n^2)\)，做法题了，只与障碍物有关。
有考虑容斥的想法，但是感觉不好做而且没时间了，所以直接跳了（\(3.5\) 个小时两小时多调 C 还想切 D?）。
首先是题目里面非常白给给我们的总方案数为（不考虑障碍物，原题没给） \(\binom{H+W-2}{H-1}\)，那妥妥的告诉了我们如果在大空地上，从 \((a,b)->(c,d)\) 的方案数是 \(\binom{c-a+d-b}{c-a}\)。
为什么呢？
不难发现，从 \((a,b)->(c,d)\)，我们一定会向右走 \(c-a\) 步，向下走 \(d-b\) 步，只不过是顺序的差别，那我们不妨把向右固定，把向下的操作插进向右的操作之中，那不就变成了典型的有 \(c-a\) 个小球，在这些小球中插入 \(d-b\) 块板，可以插在同一个地方的问题了吗，方案数显然为 \(\binom{(c-a)+(d-b)}{c-a}\)。
正难则反，考虑容斥。
然后我们令 \(con_i\) 表示不经过其他障碍物的情况下，走到第 \(i\) 个障碍物的方案数，那么很显然可以得到结果为总方案减去经过之前的障碍物走到这里的方案，具体为：
然后就做完了。
\(Code\)
int n,m,g;
typedef long long ll;
typedef pair<int,int> PII;
PII a[3003];
const ll mod=1e9+7;
ll fac[200005],ifac[200005],con[3003],ans;
ll qpow(ll x,ll w){
ll res=1;
for(;w;w>>=1,x=x*x%mod)if(w&1)res=res*x%mod;
return res;
}
void init(){
fac[0]=1;
for(ll i=1;i<=n+m;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n+m]=qpow(fac[n+m],mod-2);
for(ll i=n+m-1;~i;--i)
ifac[i]=ifac[i+1]*(i+1)%mod;
}
inline ll C(ll x,ll y){
return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
int main(){
n=read(),m=read(),g=read();
for(int i=1;i<=g;i++)
a[i].first=read(),a[i].second=read();
sort(a+1,a+1+g);
init();
for(int i=1;i<=g;i++){
int x=a[i].first,y=a[i].second;
con[i]=C(x+y-2,x-1);
for(int j=1;j<i;j++){
int xx=a[j].first,yy=a[j].second;
if(xx<=x&&yy<=y){
con[i]=(con[i]-con[j]*C(x-xx+y-yy,x-xx)%mod+mod)%mod;
}
}
ans=(ans+con[i]*C(n-x+m-y,n-x)%mod)%mod;
}
cout<<(C(n+m-2,n-1)-ans+mod)%mod;
return 0;
}