看到这套题，我的心情是这样的：
膜拜神犇NiroBC屠题+卖萌两不误。
T1
出题人十分懒惰，出了一道二合一题。
已知序列A，每个元素均为1~m之间的整数
Task1：求满足gcd(A1,A2,...,An)=k的序列数。
Task2：求满足k|lcm(A1,A2,...,An)的序列数。
要求K=[l,r]均求出答案并将它们加起来作为最终结果。
由于昨天恰好做到一道SB模板题，发现Task1可以用莫比污斯反演，具体请看BZOJ1101。
最终的答案就是：
[tex]\sum^{r}_{k=l}\sum^{\lfloor\frac{m}{k}\rfloor}_{d=1}\mu[d]*\lfloor\frac{\lfloor\frac{m}{k}\rfloor}{d}\rfloor^n[/tex]
发现[m/k]和[[m/k]/d]不同取值最多都只有m0.5个，那么相同的取值就可以一起算，复杂度降为O(mlogn)。
Task2被巫妖王屠了，在午饭时间传道。
枚举K，那么需要序列中某些数包含了K的因数，于是先将K质因数分解。
可以将相同的质因数合并，反正最后分解出来的因数也是互质的。
考虑容斥，若任意Ai都不是K的某个因数的倍数，那么这个序列肯定是不合法的。
枚举分解出来的因数，再次利用容斥来算出它对答案的贡献即可。
画外音：
此题还是一道Jb卡常题，Task1因为优化写得太丑被卡T15分，Task2因为分解质因数太丑也被卡T15分。
T2
这是一道送分题。（然而我只拿了50分）
n个盒子，每个盒子中有若干气球，m个熊孩纸，若编号在[li,ri]之间的盒子中都没有气球，那么该熊孩纸就会高兴。
q个操作，每个操作取出一个盒子中的一个气球，并询问有多少个熊孩纸是高兴的。
强制在线。
巫妖王一眼就把这题A了太神啦！！！
首先是学前班难度的结论：
1、当且仅当一个盒子的气球被取完是会对答案产生影响。
2、空盒子必然由若干段连续的区间构成，新产生一个空盒子，可能会导致两段区间的合并。
假设当前产生了空盒子i，[L,i-1][i+1,R]均为空盒子，那么新增的高兴的熊孩纸必然满足L<=li<=i<=ri<=R。
这个只要用主席树就可以兹磁。
对于空盒子区间的维护，并查集和链表都可以。
T3
这是一道画风奇异的提答题。
亮瞎了窝的24K钛合金狗眼。
下面给出画风奇异的bgm。
有一张n*m的地图，你操控一名角色，该角色起始位置x,y，移动速度v，擦弹半径为D，中弹半径为d，角色可以向八个方向移动或原地不动。
有q个子弹，子弹的出现时间为sti，消失时间为edi，x,y方向的移动速度分别为xi,yi，半径为Di，擦弹得分为Si。
每个时刻t，以角色的位置为圆心，半径为D的圆若与以子弹位置为圆心，半径为Di的圆相交，则获得擦弹得分。
每个时刻t，以角色的位置为圆心，半径为d的圆若与以子弹位置为圆心，半径为Di的圆相交，则角色在时刻t中弹。
若角色在[l,r]时刻内均没有中弹，则获得一定的不中弹得分。
构造移动操作序列，使得分最大化。
首先进入脑海的，是Gold_7大神犇的Bogo算法：
用屁股在键盘上碾一下得到序列，然后用checker来测试得分，取得分最大的序列。
然而这操作的难度过高，只好用较次的算法：只往四个方向走，设计估价函数，然后dp，可以有20~40分。
如果还是不会，可以退而求其次，原地不动，等子弹来撞。
根据数据的特点设计操作序列，可以获得高分。
Task1
子弹数量很少且不会动，地图很小，直接手玩即可获得满分。
Task2
子弹都不会动。
有一个巨大的子弹保证每个时刻你只能在(0,0)(0,10)(10,0)(10,10)这四个点移动，你的速度为10，每个时刻这四个点中有三个是有子弹的，且擦弹没有得分。
那么如果能走到安全点就走，不能走就原地待着，就有4分。
随便搞一搞应该就有10分。
Task3
只有擦弹得分，且子弹都不会动，所有子弹构成一个三角形，在上一行擦两个弹不如在下一行擦一个弹优，总共只有30步。
无脑往下然后再往右，就有8分。
dp一下就可以玩出10分啦！
Task4~10以后再看。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int mod=1000000007;
const int M=10000010;
int cas,opt,n,m,l,r,i,j,cnt,tmp;
int ss[M],prime[M>>3],a[1010],f[1010],F[1010];
ll ans,u[M];
inline ll quickmi(ll x,int y){
ll ans=1;
while (y){
if (y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
inline ll solve(int x){
int now=0;
ll ans=0;
for (int i=1;i<=x;i=now+1){
now=x/(x/i);
ans=(ans+(u[now]-u[i-1])*quickmi(x/i,n)%mod+mod)%mod;
}
return ans;
}
int main(){
u[1]=1;
for (i=2;i<=10000000;i++){
if (!ss[i])prime[++cnt]=i,u[i]=-1;
for (j=1;j<=cnt&&i*prime[j]<=10000000;j++){
ss[i*prime[j]]=1;
if (!(i%prime[j])){u[i*prime[j]]=0;break;}
else u[i*prime[j]]=-u[i];
}
}
scanf("%d%d",&cas,&opt);
if (opt==1){
for (i=2;i<=10000000;i++)u[i]+=u[i-1];
while (cas--){
scanf("%d%d%d%d",&n,&m,&l,&r);
int now;
ll ans=0;
for (i=l;i<=r;i=now+1){
now=min(r,m/(m/i));
ans=(ans+solve(m/i)*(now-i+1)%mod)%mod;
}
printf("%lld\n",ans);
}
}else{
while (cas--){
ans=0;
scanf("%d%d%d%d",&n,&m,&l,&r);
for (i=l;i<=r;i++){
cnt=0;
int p=i;
for (j=1;j<=20;j++)
if (!(p%prime[j])){
a[++cnt]=1;
while (!(p%prime[j]))p/=prime[j],a[cnt]*=prime[j];
if (p==1)break;
}
if (p!=1)a[++cnt]=p;
f[0]=0,F[0]=1;
for (j=1;j<1<<cnt;j++)
for (int k=1;k<=cnt;k++)
if (j&(1<<(k-1))){f[j]=f[j^(1<<(k-1))]+1;F[j]=F[j^(1<<(k-1))]*a[k];break;}
for (j=0;j<1<<cnt;j++){
ll now=0;
for (int k=0;k<1<<cnt;k++)
if ((j&k)==k){
if (f[k]&1)now-=m/F[k];else now+=m/F[k];
}
if (f[j]&1)ans=(ans-quickmi(now,n)+mod)%mod;
else ans=(ans+quickmi(now,n))%mod;
}
}
printf("%lld\n",ans);
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int n,m,i,x,y,q,cnt,edgenum,ans;
int a[M],fa[M],FA[M],head[M],vet[M],next[M],root[M];
struct node{int l,r,w;}tree[M*20];
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
}
int searchl(int x){
return FA[x]==x?x:FA[x]=searchl(FA[x]);
}
int searchr(int x){
return fa[x]==x?x:fa[x]=searchr(fa[x]);
}
void update(int x,int l,int r,int &p){
tree[++cnt]=tree[p];p=cnt;tree[p].w++;
if (l==r)return;
int mid=l+r>>1;
if (x<=mid)update(x,l,mid,tree[p].l);
else update(x,mid+1,r,tree[p].r);
}
int query(int x,int y,int l,int r,int p){
if (x==l&&y==r)return tree[p].w;
int mid=l+r>>1;
if (y<=mid)return query(x,y,l,mid,tree[p].l);
else if (x>mid)return query(x,y,mid+1,r,tree[p].r);
else return query(x,mid,l,mid,tree[p].l)+query(mid+1,y,mid+1,r,tree[p].r);
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
}
for (i=1;i<=n;i++){
root[i]=root[i-1];
for (int e=head[i];e;e=next[e]){
int v=vet[e];
update(v,1,n,root[i]);
}
}
for (i=1;i<=n;i++)fa[i]=i,FA[i]=i;
scanf("%d",&q);
while (q--){
scanf("%d",&x);
x=(x+ans-1)%n+1;
a[x]--;
if (!a[x]){
fa[x-1]=x;
FA[x+1]=x;
int l=searchl(x),r=searchr(x);
ans+=query(x,r,1,n,root[x])-query(x,r,1,n,root[l-1]);
}
printf("%d\n",ans);
}
}
评论 (0)
