2018-8-1题解

目录：

• A
• B
• C

A

题面

小 A 同学得到了一条⻓为L米的白色绳子,但是他觉得这条绳子的颜色过于单调了,于是他决定给绳子染上色让它变成一条彩绳。小 A 一共有m种颜色,他将L米⻓的绳子平均划分成了L小段,显然,每一小段的⻓度为 1米,然后给每一小段都染上一种颜色,每种颜色都可以染无数次,不必全部使用。

但是考虑到⻢上就要举办同学聚会了,于是他决定将这条⻓为L米的绳子顺次截成n条,第i条的⻓度为$l_i$米,以用来送给n个好朋友。为了让他的好朋友对他们收到的礼物很满意,小A觉得,送给每个人的单独的一条绳子中,不能出现相邻的两小段颜色相同的情况。同时,为了让同学们感觉到他收到的礼物很特殊,小 A 想让任意相邻的两条绳子的颜色种类不完全相同,相邻两条绳子颜色种类不完全相同指的是至少存在一种颜色,使得它不会同时出现在相邻两条绳子上。

那么,现在小 A 想知道,他有多少种不同的染色方案,两种染色方案不同,指的是原来在初始的L中的位置上至少存在一个小段使得它所染的颜色不相同。答案对p取膜输出

$n\le 1000000,m\le 1000000,l_i\le 5000,2\le p\le 10^9$

题解

先把膜数放到一边。

设$S=\max\{l_i\}$

设$f_{i,j}$表示用i种颜色染j小段（全部用上）的方案数。

考虑最后一段的颜色在前面是否出现过。则$f_{i,j}=if_{i-1,j-1}+(i-1)f_{i,j-1}$

设$dp_{i,j}$表示前i-1条已经染完了，第i条恰好用j种颜色的方案数。预处理$O(S^2)$

枚举第i-1条用的颜色数k，如果k=j，那么第i条颜色的选取方案会少一种（去掉重复的方案）。否则就是$\binom{m}{j}$

那么$dp_{i,j}=(\sum\limits_k dp_{i-1,k}(\binom{m}{j}-[j=k]))f_{j,l_i}$

这样就能$O(LS)$转移辣！

记$s_i=\sum\limits_{j} dp_{i,j}$

那么$dp_{i,j}=(s_i\binom{m}{j}-dp_{i-1,j})f_{j,l_i}$

时间复杂度$O(L+S^2)$

但是遇到了两个问题：1.空间 2.$\binom{m}{i}$预处理

空间很好解决，可以直接滚动数组优化掉，也可以把$dp_{i,j}$存进$dp_{\sum\limits_{k=1}^{i-1}l_k+j}$，空间复杂度$O(L)$。

$\binom{m}{i}$预处理可以用exlucas。由于每次计算组合数p固定，很多东西可以预处理，并且由于$m\le 10^6$所以可以在一些地方优化下。

具体见代码

/*
Author: CNYALI_LK
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
ll p;
namespace exlucas{
    ll a[102424],b[102424],c[102424],d[102424],t;
    ll sp;
    vector<ll> f[128];
    ll fpm(ll a,ll b,ll p){
        ll c;
        for(c=1;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
        return c;
    }
    void fac(ll n,ll t,ll &x,ll &y){
        x=1;y=0;
        ll p=c[t],pp=a[t];
        while(n){
            x=x*((n/pp)?fpm(f[t][pp],n/pp,pp):1)%pp*f[t][n%pp]%pp;
            n/=c[t];
            y+=n;
        }
    }
    void exgcd(ll a,ll b,ll &x,ll &y){
        if(!b){
            x=1,y=0;
        }
        else{
            exgcd(b,a%b,y,x);
            y-=(a/b)*x;
        }
    }
    ll inv(ll a,ll p){
        ll x,y;
        exgcd(a,p,x,y);
        return (x%p+p)%p;
    }
    void C(ll n,ll m,ll t){
        ll xa,ya,xb,yb,xc,yc;
        fac(n,t,xa,ya);
        fac(m,t,xb,yb);
        fac(n-m,t,xc,yc);
        ll xx,yy;
        yy=ya-yb-yc;
        xx=xa*inv(xb*xc%a[t],a[t])%a[t];
        while(yy){
            xx=xx*c[t]%a[t];
            --yy;
        }
        b[t]=xx;
    }
    ll CRT(ll t,ll mul){
        ll ans=0,iv,is;
        for(ll i=1;i<=t;++i){
            is=mul/a[i];
            iv=inv(is,a[i]);
            ans=(ans+is*iv%mul*b[i])%mul;
        }
        return ans;
    }
    void init(ll t){
        f[t].push_back(1LL);
        for(ll i=1;i<=a[t]&&i<=1000000;++i){
            f[t].push_back(f[t][i-1]);
            if(i%c[t])f[t][i]=f[t][i]*i%a[t];
        }
    }
    void Set(ll p){
        sp=p;
        t=0;
        for(ll i=2;i*i<=p;++i)
            if(!(p%i)){
                c[++t]=i;
                a[t]=1;
                d[t]=0;
                while(!(p%i)){
                    a[t]*=i;
                    ++d[t];
                    p/=i;
                }
                init(t);
            }
        if(p>1){
            c[++t]=p;
            a[t]=p;
            d[t]=1;
            init(t);
        }
    }
    ll exlucas(ll n,ll m){
        for(ll i=1;i<=t;++i){
            C(n,m,i);
        }
        return CRT(t,sp);
    }
}
ll C[1024242];
ll l[1024242],qz[1024242],f[10242424],su[1024242];
ll spm[5005][5005];
ll ff(ll x,ll y){return y<=l[x]?f[qz[x]+y]:0;}
ll fpm(ll a,ll b,ll p){
    ll c=1;
    for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
    return c;
}
ll prime(ll x){
    for(ll i=2;i*i<=x;++i)if(!(x%i))return 0;
    return 1;
}
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    ll n,m;
    n=read();m=read();p=read();
    exlucas::Set(p);
    for(ll i=0;i<=m&&i<=5000;++i){C[i]=exlucas::exlucas(m,i);}
    spm[1][1]=1;
    for(ll i=2;i<=5000;++i){
        for(ll j=1;j<=5000;++j)spm[i][j]=((i-1)*spm[i][j-1]+i*spm[i-1][j-1])%p;
    }

    for(ll i=1;i<=n;++i){
        l[i]=read();
        qz[i]=l[i-1]+qz[i-1];
    }
    su[0]=1;
    for(ll i=1;i<=n;++i){
        su[i]=0;
        for(ll j=1;j<=l[i]&&j<=m;++j){
            f[qz[i]+j]=(su[i-1]*C[j]%p-ff(i-1,j)+p)%p*spm[j][l[i]]%p;
            su[i]=(su[i]+f[qz[i]+j])%p;
        }
    }
    printf("%lld\n",su[n]);
    return 0;
}

B

题意

一棵以1为根的树，其中一些点是关键点。

两个操作：

• 给定点u，对于所有关键点v，$ans_{lca(u,v)}$加上$w_v=v$
• 给定点u 如果u是关键点，让它不是关键点 否则让它是关键点

$n,m\le 3\cdot10^5$

题解

树链剖分假做法

我们记$a_i$为i子树ans和。$b_i$为i子树关键点w的和。

那么操作1就是对u所有祖先的$a_i$加上$b_i$

操作2就是修改u所有祖先的$b_i$。

暴力可以过随机数据。

然后可以树链剖分优化。

但是卡暴力的数据树链剖分很快，随机数据树链剖分很慢。

真做法

对每个点记一个时间线段树，表示每个时间的操作。

然后线段树合并就可以了。

/*
Author: CNYALI_LK
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define aint(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}

int a[302424],to[602323],lst[602323],beg[302423],e,b[302424],fa[302424];
void add(int u,int v){
    to[++e]=v;
    lst[e]=beg[u];
    beg[u]=e;
}
ll asum[19982443],bsum[19982443],ans[302423];
int l[19982443],r[19982443],t,rt[302423];
void adda(int rt,int ls,int rs,int id,int w){
    asum[rt]+=w;
    if(ls==rs)return;
    int mid=((ls+rs)>>1);
    if(id<=mid){
        if(!l[rt])l[rt]=++t;
        adda(l[rt],ls,mid,id,w);
    }
    else{
        if(!r[rt])r[rt]=++t;
        adda(r[rt],mid+1,rs,id,w);
    }
}

void addb(int rt,int ls,int rs,int id){
    ++bsum[rt];
    if(ls==rs)return;
    int mid=((ls+rs)>>1);
    if(id<=mid){
        if(!l[rt])l[rt]=++t;
        addb(l[rt],ls,mid,id);
    }
    else{
        if(!r[rt])r[rt]=++t;
        addb(r[rt],mid+1,rs,id);
    }
}
int merge(int u,int v,int x){
    if(!v)return u;
    if(!u)return v;
    ans[x]+=asum[l[u]]*bsum[r[v]];
    ans[x]+=asum[l[v]]*bsum[r[u]];
    int mg=++t;
    asum[mg]=asum[u]+asum[v];
    bsum[mg]=bsum[u]+bsum[v];
    l[mg]=merge(l[u],l[v],x);
    r[mg]=merge(r[u],r[v],x);
    return mg;
}
void dfs(int u,int f){
    for(int i=beg[u];i;i=lst[i])if(to[i]!=f){
        dfs(to[i],u);
        rt[u]=merge(rt[u],rt[to[i]],u);
    }
}
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    int n,m,u,v;
    n=read();m=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        rt[i]=++t;
    }
    for(int i=1;i<=n;++i)
        if(a[i])adda(rt[i],0,m,0,i);
    for(int i=1;i<n;++i){
        u=read();v=read();
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=m;++i){
        if((read())==1){
            u=read();
            addb(rt[u],0,m,i);
            if(a[u])ans[u]+=u;
        }
        else{
            u=read();
            if(a[u])adda(rt[u],0,m,i,-u);
            else adda(rt[u],0,m,i,u);
            a[u]^=1;
        }
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)printf("%lld\n",ans[i]);
    return 0;
}

C

题意

有一个n行4列的环形棋盘（第1列和第4列相连）。

定义一个初始状态为，把1到4n从上到下 从左到右放进棋盘的状态

例如n=2时：

1 2 3 4

5 6 7 8

现在把它打乱了，每次可以移动1的位置，求移动回初始状态的最小步数。

$n\le 10$

题解

这种题一看就是搜索。但是答案可能很大（虽然实际上不是很大 但还是存不下） 所以用IDA*。

一个很强的估价函数：除了1以外，每个数到它应该到的地方的距离和。显然不超过最优步数。

然后就能过 还跑得很快。

实际上从1开始随机走10000步它就不可能过了，然而出题的时候没有说 答案大于多少输出无解。

/*
Author: CNYALI_LK
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) #define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
int a[15][6];
int n,x,y;  
int g(){
    int ans=0,xx,yy;
    for(int i=1;i<=n;++i)for(int j=1;j<=4;++j)if(a[i][j]!=1){
        yy=(a[i][j]-1)%4+1;
        xx=(a[i][j]-yy)/4+1;
//      printf("%d,%d->%d,%d  %d\n",i,j,xx,yy,abs(i-xx)+min(abs(yy-j),4-abs(yy-j)));
        ans+=abs(i-xx)+min(abs(yy-j),4-abs(yy-j));
    }
    return ans;
}
int idastar(int up,int f,int pre){
    int hg=g();
    if(!hg){
        return 1;
    }
    if(f+hg>up)return 0;
    if(x!=1 && pre!=2){
        swap(a[x][y],a[x-1][y]);
        --x;
        if(idastar(up,f+1,1)){
            return 1;
        }
        ++x;
        swap(a[x][y],a[x-1][y]);
    }
    if(x!=n&&pre!=1){
        swap(a[x][y],a[x+1][y]);
        ++x;
        if(idastar(up,f+1,2)){
            return 1; } --x;
        swap(a[x][y],a[x+1][y]);
    }
    if(pre!=4){
        swap(a[x][y],a[x][y%4+1]);
        y=y%4+1;
        if(idastar(up,f+1,3)){
            return 1;
        }
        y=(y+2)%4+1;
        swap(a[x][y],a[x][y%4+1]);
    }
    if(pre!=3){
        swap(a[x][y],a[x][(y+2)%4+1]);
        y=(y+2)%4+1;
        if(idastar(up,f+1,4)){
            return 1;
        }
        y=y%4+1;
        swap(a[x][y],a[x][(y+2)%4+1]);
    }
    return 0;
}
int main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i)for(int j=1;j<=4;++j)if(1==(a[i][j]=read())){x=i,y=j;};
    int ans=g();
    while(!idastar(ans,0,0))++ans;
    printf("%d\n",ans);
    return 0;
}