[SDOI2017]Round 1

day1

数字表格

Description
\(fib[i]= \begin{cases}0 & i=0 \\ 1&i=1\\ fib[n]=fib[n-1]+fib[n-2]&n\leq2\end{cases}\)

对于一个\(n\times{m}\)的表格,第\(i\)行第\(j\)列的格子中的数是\(f[(i,j)]\),求表格中的数的积,答案对\(10^9+7\)取模.

HINT
多组数据, \(T\leq1000,1\leq{n},m\leq10^6\).

Solution
设 \(F(x)\) 表示 \(x|(i,j)(i\leq{n},j\leq{m})\) 的个数,则 \(F(x)=\lfloor\frac{n}{x}\rfloor\times\lfloor\frac{m}{x}\rfloor\).

设 \(f(x)\) 表示 \((i,j)=x(i\leq{n},j\leq{m})\) 的个数,则 \(F(d)=\sum_{d|g}f(g)\).

莫比乌斯反演一下,

\(\begin{split}f(d)&=\sum_{d|g}\mu(\frac{g}{d})F(g)\\&=\sum_{d|g}\mu(\frac{g}{d})\times\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor\end{split}\)

即
\(\begin{split}ans&=\prod_{d=1}^{min(n,m)}fib[d]^{f(d)}\\&=\prod_{d=1}^{min(n,m)}fib[d]^{\sum_{d|g}\;\mu(\frac{g}{d})\times\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor}\\&=\prod_{g=1}^{min(n,m)}(\prod_{d|g}fib[d]^{\mu(\frac{g}{d})})^{\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor}\end{split}\)

因为 \(\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor\) 的取值是 \(\sqrt{n}\) 个的,所以记录 \(\prod_{d|g}fib[d]^{\mu(\frac{g}{d})}\) 的关于 \(g\) 的前缀积 , 枚举 \(\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor\) 的取值 即可.

#define K 80000
#define N 1000001
#define M 1000000007
int f[N],rev[N],s[N],mu[N],p[K],n,m,t,cnt,ans;
bool b[N];
inline void prime(){
    mu[1]=1;
    for(int i=2;i>=1;
    }
    return ret;
}
inline void Aireen(){
    prime();
    f[0]=0;f[1]=1;
    for(int i=2;i=M) f[i]-=M;
    }
    for(int i=0;i

树点涂色

Description
给定一棵n个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同.
定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色.Bob可能会进行这几种操作:

  • 1 x:把点x到根节点的路径上所有的点染上一种没有用过的新颜色.
  • 2 x y:求x到y的路径的权值.
  • 3 x y:在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值.

Bob一共会进行m次操作.

HINT
\(1\leq{n,m}\leq100000\).

Solution
记 \(f(x)\) 表示 \(x\) 与其父亲的颜色是否相同 ( 相同为 \(0\) , 不同为 \(1\) ) , 默认 \(f(x)=1\) .

显然一个点到根的路径权值为路径上的 \(f(x)\) 之和 , 记为 \(g(x)\) .

\((u,v)\)的路径权值为 \(g(u)-g(v)-2(lca(u,v))+1\) .

所以只需按 \(dfs\) 序建棵线段树 , 维护区间 \(g(x)\) 最大值.

操作一相当于 \(access\) 操作 , 将路径上原来的 \(preferred\;child\) 子树中的 \(g(x)+1\),将 \(access\) 后的 \(preferred\;child\) 子树中的 \(g(x)-1\)

#define N 100005
#define M 1000005
struct graph{
    int nxt,to;
}e[N<<1];
int g[N],n,m,cnt,tot;
inline void addedge(int x,int y){
    e[++cnt]=(graph){g[x],y};g[x]=cnt;
}
inline void adde(int x,int y){
    addedge(x,y);addedge(y,x);
}
int l[N],r[N],p[N],fa[N],dep[N],siz[N],son[N],top[N];
inline void dfs1(int u){
    int mx=0;siz[u]=1;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dep[e[i].to]){
            fa[e[i].to]=u;
            dep[e[i].to]=dep[u]+1;
            dfs1(e[i].to);
            siz[u]+=siz[e[i].to];
            if(siz[e[i].to]>mx){
                son[u]=e[i].to;
                mx=siz[e[i].to];
            }
        }
}
inline void dfs2(int u,int tp){
    top[u]=tp;p[++cnt]=u;l[u]=cnt;
    if(son[u]) dfs2(son[u],tp);
    for(int i=g[u];i;i=e[i].nxt)
        if(e[i].to!=son[u]&&e[i].to!=fa[u])
            dfs2(e[i].to,e[i].to); 
    r[u]=cnt;
}
inline int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]>1;
        build(lef,l,mid);build(rig,mid+1,r);
        lt[u].mx=max(lt[lef].mx,lt[rig].mx);
    }
    else lt[u].mx=dep[p[lt[u].l]];
}
inline void pushdown(int u){
    if(lt[u].l==lt[u].r||!lt[u].lzy) return;
    int lef=u<<1,rig=u<<1|1;
    lt[lef].mx+=lt[u].lzy;
    lt[rig].mx+=lt[u].lzy;
    lt[lef].lzy+=lt[u].lzy;
    lt[rig].lzy+=lt[u].lzy;
    lt[u].lzy=0;
}
inline void add(int u,int l,int r,int k){
    if(lt[u].l>=l&<[u].r<=r){
        lt[u].mx+=k;lt[u].lzy+=k;return;
    }
    if(lt[u].l>1;
        if(l<=mid) add(lef,l,r,k);
        if(r>mid) add(rig,l,r,k);
        lt[u].mx=max(lt[lef].mx,lt[rig].mx);
    }
}
inline int ask(int u,int l,int r){
    if(lt[u].l>=l&<[u].r<=r)
        return lt[u].mx;
    if(lt[u].l>1;
        if(l<=mid) ret=max(ret,ask(lef,l,r));
        if(r>mid) ret=max(ret,ask(rig,l,r));
        return ret; 
    }
}
inline int asks(int u,int v){
    int k=lca(u,v);
    return ask(1,l[u],l[u])+ask(1,l[v],l[v])-2*ask(1,l[k],l[k])+1;
}
struct LCT{
    int c[2],f;
}tr[N];
inline bool isroot(int u){
    return tr[tr[u].f].c[0]!=u&&tr[tr[u].f].c[1]!=u;
}
inline bool sn(int u){
    return tr[tr[u].f].c[1]==u;
}
inline void ins_p(int f,int u,int c){
    tr[f].c[c]=u;tr[u].f=f;
}
inline void rotate(int u){
    int f=tr[u].f,c=sn(u);
    if(isroot(f)) tr[u].f=tr[f].f;
    else ins_p(tr[f].f,u,sn(f));
    ins_p(f,tr[u].c[c^1],c);
    ins_p(u,f,c^1);
}
inline void splay(int u){
    while(!isroot(u)){
        if(isroot(tr[u].f)) rotate(u);
        else if(sn(u)==sn(tr[u].f)){
            rotate(tr[u].f);rotate(u);
        }
        else{
            rotate(u);rotate(u);
        }
    }
}
inline int lef(int u){
    while(tr[u].c[0]) u=tr[u].c[0];
    return u;
}
inline void access(int u){
    for(int lst=0,y;u;lst=u,u=tr[u].f){
        splay(u);
        y=lef(lst);
        if(y) add(1,l[y],r[y],-1);
        y=lef(tr[u].c[1]);
        if(y) add(1,l[y],r[y],1);
        tr[u].c[1]=lst;
    }
}
inline void Aireen(){
    n=read();m=read();
    for(int i=1;i

序列计数

Description
对于一个长度为 \(n\) 的合法序列,要求 \(\forall{1\leq{i}\leq{n}},0<{a_i}\leq{m},p|\sum_{i=1}^{n}a_i,\)这 \(n\) 个数中,至少有一个数是质数.求有多少合法序列.

HINT
\(1\leq{n}\leq10^9,1\leq{m}\leq2\times10^7,1\leq{p}\leq100\).

Solution
答案为所有和为 \(p\) 的倍数的情况-没有质数且和为 \(p\) 的倍数的情况.

\(f[i][j]\) 表示前 \(i\) 个数和 \(mod\;p=j\) 的方案数.

\(f[i][j]=f[i-1][k]\times g[(j-k+p)\;mod\;p]\;(g[i]\)表示可以填的数中 \(mod\;p=i\) 的数的个数\().\)

矩乘优化一下即可.

#define P 100
#define K 1300000
#define N 20000001
#define M 20170408
struct matrix{
    int a[P][P],n,m;
    inline void init(){
        memset(a,0,sizeof(a));
        for(int i=0;i=M) c.a[i][j]-=M;
            }
    return c;
}
inline matrix po(matrix x,int k){
    matrix ret;ret.init();ret.n=ret.m=x.n;
    while(k){
        if(k&1) ret=ret*x;
        x=x*x;k>>=1;
    }
    return ret;
} 
inline void Aireen(){
    scanf("%d%d%d",&n,&m,&p);
    prime(m);
    a.n=p;a.m=1;
    a.a[0][0]=1;
    b.n=b.m=p;
    for(int j=0;j

day2

新生舞会

Description
男女生两两配对跳舞,第i个男生与第j个女生一起跳舞的喜悦程度为\(a_{i,j}\),不喜悦程度为\(b_{i,j}\),求\(\frac{\sum{a_i}}{\sum{b_i}}\)的最大值.
HINT
\(1\leq{n}\leq100,1\leq{a_{i,j},b_{i,j}}\leq10^4\).
Solution
二分\(C=\frac{\sum{a_i}}{\sum{b_i}}\),

判断是否存在\(\sum{a_i}\geq{C\times\sum{b_i}}\),即\(\sum{a_i}-{\sum{b_i\times{C}}}\geq0\)

建立二分图,\((i,j)=a_{i,j}-b_{i,j}\times{C}\),用KM求二分图最大权匹配.

#define N 101
#define INF 1e7
#define eps 1e-7
int fr[N],n;
bool vx[N],vy[N];
double a[N][N],b[N][N],w[N][N],x[N],y[N],sla[N];
inline bool match(int u){
    double tmp;vx[u]=true;
    for(int j=1;j<=n;++j){
        if(vy[j]) continue;
        tmp=x[u]+y[j]-w[u][j];
        if(fabs(tmp)sla[j]) tmp=sla[j];
            for(int j=1;j<=n;++j)
                if(vx[j]) x[j]-=tmp;
            for(int j=1;j<=n;++j)
                if(vy[j]) y[j]+=tmp;
                else sla[j]-=tmp;
        }
    }
    double cnt=0.0,sum=0.0;
    for(int i=1;i<=n;++i)
        cnt+=a[fr[i]][i];
    for(int i=1;i<=n;++i)
        sum+=b[fr[i]][i];
    double ret=0.0;
    for(int i=1;i<=n;++i)
        ret+=w[fr[i]][i];
    return ret>-1e-13;
}  
inline bool chk(double k){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            w[i][j]=a[i][j]-b[i][j]*k;
    return KM();
}
inline void Aireen(){
    double mxa=0.0,mia=1e4,mxb=0.0,mib=1e4;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            scanf("%lf",&a[i][j]);
            mxa=max(mxa,a[i][j]);
            mia=min(mia,a[i][j]);
        }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            scanf("%lf",&b[i][j]);
            mxb=max(mxb,b[i][j]);
            mib=min(mib,b[i][j]);
        }
    double l=mia/mxb,r=mxa/mib,mid;
    while(l+eps

硬币游戏

Description
n个人各猜一个长度为\(m\)的H/T序列,扔很多次硬币,记录下落后的翻面情况,得到一个硬币序列.如果有人的序列为硬币序列的子序列,游戏结束,此人获胜.保证不存在相同的序列.
HINT
\(1\leq{n,m}\leq300\).
Solution
设N为一个未结束的状态.对于序列a,b,如果序列a的后缀是序列b的前缀,那么a会对b的胜利产生影响:\(\sum\frac{1}{2}^k\)(a的后缀a[k+1...n]是序列b的前缀)的概率a获胜.
这样列出n个方程,但是存在n+1个未知数,所以还需要所有序列的概率之和为1这个方程.

#define N 305
#define eps 1e-13
int nxt[N],n,m;
char a[N],b[N],c[N][N];
double f[N][N],mul[N],ans[N];
inline void kmp(int x,int y){
    int k=0;
    for(int i=1;i<=m;++i)
        a[i]=c[x][i],b[i]=c[y][i];
    for(int i=2,j=0;i<=m;++i){
        while(j&&b[j+1]!=b[i]) j=nxt[j];
        j+=(b[j+1]==b[i]);nxt[i]=j;
    }
    for(int i=1,j=0;i<=m;++i){
        while(j&&b[j+1]!=a[i]) j=nxt[j];
        j+=(b[j+1]==a[i]);k=j;
    }
    while(k){
        f[y][x]+=mul[m-k];k=nxt[k];
    }
}
inline void gauss(int n){
    double tmp;
    for(int i=0;i

相关分析

Description
给定n个点\((x_i,y_i)\),维护三种操作:

  1. \(1\;l\;r:\overline{x}=\sum_{i=l}^{r}\frac{x_i}{r-l+1},\overline{y}=\sum_{i=l}^{r}\frac{y_i}{r-l+1}\),求\(a=\frac{\sum_{i=l}^{r}(x_i-\overline{x})(y_i-\overline{y})}{\sum_{i=l}^{r}(x_i-\overline{x})^2}\)
  2. \(2\;l\;r\;s\;t:\)对于区间 \([l,r],x_i+s,y_i+t\).
  3. \(3\;l\;r\;s\;t:\)对于区间 \([l,r],x_i+s+i,y_i+t+i\).

HINT
\(1\leq{n,m}\leq10^5\).
Solution
把式子拆开,线段树维护.

#define N 100005
#define M 1000005
struct SegTree{
    int l,r,fl;double sx,sy,sxx,sxy,cx,cy;
}lt[M];
double X[N],Y[N];
int n,m;
inline void build(int u,int l,int r){
    lt[u].l=l;lt[u].r=r;
    if(lt[u].l>1;
        build(lef,l,mid);build(rig,mid+1,r);
        lt[u].sx=lt[lef].sx+lt[rig].sx;
        lt[u].sy=lt[lef].sy+lt[rig].sy;
        lt[u].sxx=lt[lef].sxx+lt[rig].sxx;
        lt[u].sxy=lt[lef].sxy+lt[rig].sxy;
    }
    else{
        lt[u].sx=X[lt[u].l];
        lt[u].sy=Y[lt[u].l];
        lt[u].sxx=lt[u].sx*lt[u].sx;
        lt[u].sxy=lt[u].sx*lt[u].sy;
    }
}
inline double sum(int s,int t){
    double l=1.0*s,r=1.0*t;
    return (l+r)*(r-l+1.0)/2.0;
}
inline double sqr(int s,int t){
    double l=1.0*(s-1),r=1.0*t;
    return ((r*(r+1.0)*(2.0*r+1.0))-(l*(l+1.0)*(2.0*l+1.0)))/6.0;
}
inline void down1(int u,double s,double t){
    if(!lt[u].fl) lt[u].fl=1;
    lt[u].cx+=s;lt[u].cy+=t;
    
    lt[u].sxx+=2*lt[u].sx*s+s*s*(lt[u].r-lt[u].l+1); 
    lt[u].sxy+=lt[u].sx*t+lt[u].sy*s+s*t*(lt[u].r-lt[u].l+1); 
    
    lt[u].sx+=s*(lt[u].r-lt[u].l+1);lt[u].sy+=t*(lt[u].r-lt[u].l+1);
}
inline void down2(int u,double s,double t){
    lt[u].fl=2;lt[u].cx=s;lt[u].cy=t;
    
    lt[u].sxx=s*s*(lt[u].r-lt[u].l+1)+2.0*s*sum(lt[u].l,lt[u].r)+sqr(lt[u].l,lt[u].r);
    lt[u].sxy=s*t*(lt[u].r-lt[u].l+1)+(s+t)*sum(lt[u].l,lt[u].r)+sqr(lt[u].l,lt[u].r);
    
    lt[u].sx=s*(lt[u].r-lt[u].l+1)+sum(lt[u].l,lt[u].r);
    lt[u].sy=t*(lt[u].r-lt[u].l+1)+sum(lt[u].l,lt[u].r);
}
inline void pushdown(int u){
    if(!lt[u].fl) return;
    if(lt[u].l==lt[u].r){
        lt[u].fl=0;lt[u].cx=lt[u].cy=0.0;return;
    }
    if(lt[u].fl&1){
        down1(u<<1,lt[u].cx,lt[u].cy);
        down1(u<<1|1,lt[u].cx,lt[u].cy);
        lt[u].fl=0;lt[u].cx=lt[u].cy=0.0;
        return;
    }
    down2(u<<1,lt[u].cx,lt[u].cy);
    down2(u<<1|1,lt[u].cx,lt[u].cy);
    lt[u].fl=0;lt[u].cx=lt[u].cy=0.0;
}
inline void add(int u,int l,int r,double s,double t){
    if(lt[u].l>=l&<[u].r<=r){
        down1(u,s,t);return;
    }
    if(lt[u].l>1;
        pushdown(u);
        if(l<=mid) add(lef,l,r,s,t);
        if(r>mid) add(rig,l,r,s,t);
        lt[u].sx=lt[lef].sx+lt[rig].sx;
        lt[u].sy=lt[lef].sy+lt[rig].sy;
        lt[u].sxx=lt[lef].sxx+lt[rig].sxx;
        lt[u].sxy=lt[lef].sxy+lt[rig].sxy;
    }
}
inline void cover(int u,int l,int r,double s,double t){
    if(lt[u].l>=l&<[u].r<=r){
        down2(u,s,t);return;
    }
    if(lt[u].l>1;
        pushdown(u);
        if(l<=mid) cover(lef,l,r,s,t);
        if(r>mid) cover(rig,l,r,s,t);
        lt[u].sx=lt[lef].sx+lt[rig].sx;
        lt[u].sy=lt[lef].sy+lt[rig].sy;
        lt[u].sxx=lt[lef].sxx+lt[rig].sxx;
        lt[u].sxy=lt[lef].sxy+lt[rig].sxy;
    }
} 
inline double askx(int u,int l,int r){
    if(lt[u].l>=l&<[u].r<=r)
        return lt[u].sx;
    if(lt[u].l>1;
        pushdown(u);
        if(l<=mid) ret+=askx(lef,l,r);
        if(r>mid) ret+=askx(rig,l,r);
        return ret;
    } 
}
inline double asky(int u,int l,int r){
    if(lt[u].l>=l&<[u].r<=r)
        return lt[u].sy;
    if(lt[u].l>1;
        pushdown(u);
        if(l<=mid) ret+=asky(lef,l,r);
        if(r>mid) ret+=asky(rig,l,r);
        return ret;
    } 
}
inline double askxx(int u,int l,int r){
    if(lt[u].l>=l&<[u].r<=r)
        return lt[u].sxx;
    if(lt[u].l>1;
        pushdown(u);
        if(l<=mid) ret+=askxx(lef,l,r);
        if(r>mid) ret+=askxx(rig,l,r);
        return ret;
    } 
}
inline double askxy(int u,int l,int r){
    if(lt[u].l>=l&<[u].r<=r)
        return lt[u].sxy;
    if(lt[u].l>1;
        pushdown(u);
        if(l<=mid) ret+=askxy(lef,l,r);
        if(r>mid) ret+=askxy(rig,l,r);
        return ret;
    } 
}
inline void Aireen(){
    n=read();m=read();
    for(int i=1;i<=n;++i) scanf("%lf",&X[i]); 
    for(int i=1;i<=n;++i) scanf("%lf",&Y[i]); 
    build(1,1,n);
    int ty,l,r;double x,y,ax,ay,ans;
    while(m--){
        ty=read();l=read();r=read();
        if(ty==1){
            x=askx(1,l,r);y=asky(1,l,r);
            ax=x/(r-l+1);ay=y/(r-l+1);
            ans=askxy(1,l,r)-ax*y-ay*x+ax*ay*(r-l+1);
            ans/=(askxx(1,l,r)-2.0*ax*x+ax*ax*(r-l+1));
            printf("%.10lf\n",ans);
        }
        else if(ty==2){
            scanf("%lf%lf",&x,&y);
            add(1,l,r,x,y);
        }
        else{
            scanf("%lf%lf",&x,&y);
            cover(1,l,r,x,y);
        }
    }
}

2017-04-21 10:23:13

DPKMPLCT二分高斯消元矩乘莫比乌斯反演线段树KM

相关

DP决策优化小结

dp专题练习

牛客练习赛91（并查集+二维偏序+二分）

腾讯云搭建个人博客wordpress

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

Java高并发，ThreadPoolExecutor线程池技术

数据结构与算法之PHP查找算法（二分查找）

sqlserver with(NOLOCK) 或 with(READPAST）

二分查找模板（准确找定值）

浅谈二分的边界问题

单调队列优化DP历险记

标签

一品网 冀ICP备14022925号-6