首页 > 代码库 > SDOI2017 Round1 Day1 题解 （BZOJ4816 BZOJ4817 BZOJ4818）
SDOI2017 Round1 Day1 题解 （BZOJ4816 BZOJ4817 BZOJ4818）
不知道有几个AK的，除了出题人SB搬了个BZOJ3779以外，应该没什么因素阻碍AK吧。要是SCOI考这套题多好。
BZOJ4816 数字表格
SB反演，推出$ans=\prod_{i=1}^nf^{\sum_{j=1}^{\left\lfloor\frac ni\right\rfloor}\mu(j)\left\lfloor\frac n{ij}\right\rfloor\left\lfloor\frac m{ij}\right\rfloor}(i)$，直接$O(n^{\frac34}+n^{\frac12}logn)$计算。
#include<algorithm>
#include<cstdio>
using namespace std;
typedef unsigned long long ll;
const int p=1e9+7;
const int N=1e6+5;
ll wop(ll a,ll n){
ll s=1;
for(;n;n>>=1){
if(n&1)s=s*a%p;
a=a*a%p;
}
return s;
}
ll f[N],g[N];
int r[N];
bool vis[N];
ll sol(int n,int m){
ll s=0;
int i=1;
while(i<=n){
int j=min(n/(n/i),m/(m/i));
s+=(g[j]-g[i-1])*(n/i)*(m/i);
i=j+1;
}
return s;
}
int main(){
f[1]=1;
for(int i=2;i<N;++i)
f[i]=(f[i-1]+f[i-2])%p;
f[0]=1;
for(int i=1;i<N;++i)
(f[i]*=f[i-1])%=p;
g[1]=1;
int l=0;
for(int i=2;i<N;++i){
if(!vis[i])
g[r[l++]=i]=-1;
for(int*j=r;;++j){
if(i**j>=N)break;
vis[i**j]=1;
if(i%*j==0)break;
g[i**j]=-g[i];
}
}
for(int i=2;i<N;++i)
g[i]+=g[i-1];
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
ll s=1;
int i=1;
while(i<=n){
int j=min(n/(n/i),m/(m/i));
(s*=wop(f[j]*wop(f[i-1],p-2)%p,sol(n/i,m/i)))%=p;
i=j+1;
}
printf("%lld\n",s);
}
}
BZOJ4817 树点涂色
做法同BZOJ3779。
#include<algorithm>
#include<cstdio>
#define I (J+1)
#define J (i+j>>1)
#define P (k<<1)
#define S (P^1)
using std::max;
const int N=1e5+5;
int n,dfn;
typedef int arr[N];
arr c1,c2,c3,c4,c5,f1,f2,g;
struct edge{
int v;
edge*s;
}e2[N*2];
edge*l=e2,*h[N];
void ins(int u,int v){
edge s={v,h[u]};
*(h[u]=l++)=s;
}
void dfs(int u){
c1[g[f1[u]=++dfn]=u]=1;
for(edge*i=h[u];i;i=i->s)
if(i->v!=c2[u]){
c3[i->v]=c3[c2[i->v]=u]+1;
dfs(i->v);
c1[u]+=c1[i->v];
if(c1[i->v]>c1[c4[u]])
c4[u]=i->v;
}
f2[u]=dfn;
}
int lca(int s,int t){
while(c5[s]!=c5[t])
c3[c5[s]]>c3[c5[t]]?s=c2[c5[s]]:t=c2[c5[t]];
return c3[s]<c3[t]?s:t;
}
namespace seg{
struct node{int d,s;}a[N*4];
void upd(int k){
a[k].s=max(a[P].s,a[S].s)+a[k].d;
}
void inc(int d,int s,int t,int i,int j,int k){
if(s<=i&&j<=t)
a[k].d+=d,a[k].s+=d;
else{
if(s<I)inc(d,s,t,i,J,P);
if(t>J)inc(d,s,t,I,j,S);
upd(k);
}
}
int ask(int s,int t,int i,int j,int k){
if(s==i&&j==t)return a[k].s;
int r=t<I?ask(s,t,i,J,P):s>J?ask(s,t,I,j,S):max(ask(s,J,i,J,P),ask(I,t,I,j,S));
return r+a[k].d;
}
}
void inc(int s,int d){
seg::inc(d,f1[s],f2[s],1,n,1);
}
struct node;
typedef node*ptr;
struct node{ptr i,j,p;}e[N];
bool root(ptr o){return o!=o->p->i&&o!=o->p->j;}
void turn(ptr o){
ptr s=o->p,t=s->p;
if(!root(s))(s==t->i?t->i:t->j)=o;
o->p=t,s->p=o;
if(o==s->i)
s->i=o->j,o->j->p=s,o->j=s;
else
s->j=o->i,o->i->p=s,o->i=s;
}
ptr splay(ptr o){
while(!root(o)){
if(!root(o->p))turn(o==o->p->i^o->p==o->p->p->i?o:o->p);
turn(o);
}
return o;
}
void inc(ptr&o,int d){
if(o!=e){
while(o->i!=e)o=o->i;
inc(splay(o)-e,d);
}
}
ptr exp(ptr o){
ptr s=e;
for(;o!=e;o=o->p){
inc(s,-1);
ptr t=splay(o)->j;
o->j=s,s=o;
inc(t,1);
}
return s;
}
int ask1(int u){
return seg::ask(f1[u],f2[u],1,n,1);
}
int ask2(int u){
return seg::ask(f1[u],f1[u],1,n,1);
}
int main(){
int m,o,u,v;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;++i)
scanf("%d%d",&u,&v),ins(u,v),ins(v,u);
dfs(1);
for(int i=1;i<=n;++i){
e[i]=(node){e,e,e+c2[i]};
if(c4[c2[i]]!=i)
for(int j=i;j;j=c4[j])c5[j]=i;
inc(i,1);
}
while(m--){
scanf("%d%d",&o,&u);
if(o==1)exp(e+u);
else if(o==2){
scanf("%d",&v);
printf("%d\n",ask2(u)+ask2(v)-ask2(lca(u,v))*2+1);
}else
printf("%d\n",ask1(u));
}
}
BZOJ4818 序列计数
线性筛预处理贡献，矩阵快速幂优化DP。前者复杂度$O(m)$，后者复杂度$O(p^3logn)$。注意到矩阵是循环矩阵，所以可以优化到$O(p^2logn)$，用FFT可以进一步优化到$O(plogplogn)$。
代码是$O(m+p^2logn)$的。
#include<cstdio>
#include<cstring>
typedef unsigned long long ll;
const int p=20170408;
const int N=100;
const int M=2e7+5;
int n,m,l,q1[M/10],*q2=q1,c[N][2],e1[N],e2[N],f1[N],f2[N];
bool v[M];
inline void mul(int*a,int*b){
static ll c[N];
memset(c,0,sizeof c);
for(int i=0;i<l;++i)
for(int j=0;j<l;++j)
c[(i+j)%l]+=(ll)a[i]*b[j];
for(int i=0;i<l;++i)
a[i]=c[i]%p;
}
int main(){
scanf("%d%d%d",&n,&m,&l);
for(int i=2;i<=m;++i){
if(!v[i])*q2++=i;
for(int*j=q1;j<q2;++j){
if(i**j>m)break;
v[i**j]=1;
}
++c[i%l][v[i]^1];
}
++c[1%l][0];
for(int i=0;i<l;++i){
f1[i]=c[i][0]+c[i][1];
f2[i]=c[i][0];
}
e1[0]=e2[0]=1;
for(;n;n>>=1){
if(n&1)
mul(e1,f1),mul(e2,f2);
if(n>1)
mul(f1,f1),mul(f2,f2);
}
int s=(e1[0]-e2[0]+p)%p;
printf("%d\n",s);
}
SDOI2017 Round1 Day1 题解 （BZOJ4816 BZOJ4817 BZOJ4818）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。