ZJT's Blog

大変に気分がいい~

集训队作业之ARC083-D

2017-11-29 8:32017-11-29 8:3
集训队作业AtCoder基环树DP

传送门

我们先建出一个图模型,把每个$x$坐标和$y$坐标看成顶点,把每个平面中的球看成一条边,连接相应的$x$坐标和$y$坐标。显然这个图的连通块之间是没有影响的,我们可以单独处理出每个的方案数之后再插回去。

如果某个连通块不是一棵基环树,那么答案显然是0。我们把每个点对应到它的一条邻边上面去,代表这个点最终会撞上这条边对应的球。考虑钦定环上顶点的选边,只有两种可能,分别算一下就行了。方向确定之后,点之间先后关系也确定了,然后就可以用DP处理啦。

#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#define MAXN 200010
#define LL long long
using namespace std;

const LL P=1000000007;

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int e2[MAXN][2];
int g[MAXN],nume;
int de[MAXN],dp[MAXN],fa[MAXN],tag[MAXN],size[MAXN],pre[MAXN];
int root;
vector<int> rt[MAXN],tr;
LL fac[MAXN],invfac[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

int getf(int x){
    if(fa[x]==x) return x;
    return fa[x]=getf(fa[x]);
}

void dfs(int x,int p){
    pre[x]=p;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && e[i].to!=root)
            dfs(e[i].to,x);
    if(x>pre[pre[x]]) tr.push_back(x);
}

void init(){
    fac[0]=1;
    for(int i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%P;
    invfac[MAXN-1]=getPow(fac[MAXN-1],P-2);
    for(int i=MAXN-2;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%P;
}

LL getC(int x,int y){
    return fac[x]*invfac[y]%P*invfac[x-y]%P;
}

LL dfs2(int x){
    size[x]=0;
    LL res=1;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to<pre[x]){
            LL temp=dfs2(e[i].to);
            size[x]+=size[e[i].to];
            res=res*temp%P*getC(size[x],size[e[i].to])%P;
        }
    size[x]++;
    return res;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    init();
    n<<=1;
    for(int i=1;i<=n;i++) scanf("%d%d",&e2[i][0],&e2[i][1]);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        int x=e2[i][0],y=e2[i][1]+(n/2);
        addEdge(x,y);
        addEdge(y,x);
        de[x]++; de[y]++;
        if(getf(x)!=getf(y)) fa[fa[x]]=fa[y];
        else tag[x]=tag[y]=1;
    }
    for(int i=1;i<=n;i++){
        if(getf(i)!=i) de[fa[i]]+=de[i];
        dp[fa[i]]++;
        if(tag[i]) rt[fa[i]].push_back(i);
    }
    LL ans=1;
    int ts2=0;
    for(int i=1;i<=n;i++)
        if(getf(i)==i){
            if(de[i]!=dp[i]*2){
                puts("0");
                return 0;
            }
            assert(rt[i].size()==2);
            LL res=0,res1=1;
            tr.clear();
            root=rt[i][0];
            dfs(rt[i][0],rt[i][1]);
            int ts=0;
            for(int j=0;j<tr.size();j++){
                LL temp=dfs2(tr[j]);
                ts+=size[tr[j]];
                res1=res1*temp%P*getC(ts,size[tr[j]])%P;
            }
            res=(res+res1)%P;
            tr.clear();
            root=rt[i][1];
            dfs(rt[i][1],rt[i][0]);
            ts=0;
            res1=1;
            for(int j=0;j<tr.size();j++){
                LL temp=dfs2(tr[j]);
                ts+=size[tr[j]];
                res1=res1*temp%P*getC(ts,size[tr[j]])%P;
            }
            res=(res+res1)%P;
            ts2+=ts;
            ans=ans*res%P*getC(ts2,ts)%P;
        }
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之ARC079-F

2017-10-25 9:232017-10-25 9:23
集训队作业AtCoder基环树

传送门

比较水的题,直接把环断开,设删掉了$(x,y)$这条边,并把$y$设为根节点,在树上dfs出每个点的权值(就是儿子权值的mex),然后再判断删掉的那条边合不合法。如果不合法,考虑$y$的权值等于$x$当前权值的情况,再dfs一遍,判断一下就行了。

#include <cstdio>
#include <cstring>
#define MAXN 200010

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN];

int n,root;
int g[MAXN],nume;
int p[MAXN];
bool visit[MAXN];
int f[MAXN];
bool cnt[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x){
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=root) 
            dfs(e[i].to);
    for(int i=g[x];~i;i=e[i].next) 
        if(f[e[i].to]>=0) 
            cnt[f[e[i].to]]=1;
    for(f[x]=0;cnt[f[x]];f[x]++);
    for(int i=g[x];~i;i=e[i].next) 
        if(f[e[i].to]>=0) 
            cnt[f[e[i].to]]=0;
}

bool check(){
    int x=p[root];
    for(int i=g[x];~i;i=e[i].next)
        cnt[f[e[i].to]]=1;
    bool flag=1;
    if(cnt[f[x]]) flag=0;
    for(int i=0;i<f[x];i++) if(!cnt[i]) flag=0;
    memset(cnt,0,sizeof cnt);
    return flag;
}

bool gao(){
    int x=1;
    while(!visit[x]) visit[x]=1,x=p[x];
    memset(visit,0,sizeof visit);
    memset(f,-1,sizeof f);
    root=x;
    dfs(root);
    if(check()) return 1;
    int f0=f[p[x]];
    memset(f,-1,sizeof f);
    f[root]=f0;
    dfs(root);
    if(check()) return 1;
    return 0;
}

int main(){
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",p+i),addEdge(p[i],i);
    if(gao()) puts("POSSIBLE");
    else puts("IMPOSSIBLE");
}

查看详细内容

集训队作业之AGC008-E

2017-10-24 16:592017-10-25 9:30
集训队作业AtCoder基环树

传送门

学校的网上不去atcoder了。。。可是,为什么会这样呢?明明连google都能上的。。。看题也好,交题也好,明明之前都是可以的,可是到底为什么会变成这样呢。。?

所以现在只能用手机看题+交题了,好麻烦啊。。。

这题是个比较烦的分类讨论,考虑答案的置换,我们把他拆成一些轮换来看。输入给的那坨东西可以看成一个基环树,同一个基环树中的点最终肯定在同一个轮换里,但是反过来不一定成立(关于这些后面有一些结论)。我们对每棵基环树分开统计,按照每棵基环树的结构进行分类。如果一棵基环树不是一个环(就是环上有边连出去),那他肯定是不能跟别的基环树套在同一个轮换里面的,所以可以拿他出来单独考虑。考虑环上的两个相邻的点,他们在轮换上的距离肯定小于等于2,也就是每两个环上的相邻点之间最多有一个空隙可以插进环外的点。考虑环上的某个点伸出去的子树,如果这个子树不是一条链(即某个点有不止1个儿子),则插进这些空隙里肯定无法满足条件。这样的话,去掉子树非链的情况,每个点的子树可以用一个$l_i$即伸出去的链长度来表示。对于环上的每个点$i$,我们要决策这$l_i$个点,是贴着$i$号点一个个插进空隙里,还是隔一个点,从再往前的一个空隙开始插(这样插完之后,$i$号点前的空隙就不能再插点了,就相当于插了$l_i+1$个点)。这样统计一下之后,非环的基环树就考虑完了,只剩下环的情况要考虑了。

考虑两个长度相同的环(记环长度为$l$),他们可以互相gay在一起(如"1,2,3"和"4,5,6"gay在一起就变成了"1,4,2,5,3,6"),并且根据相对位置有$l$种插法。考虑单个环,如果$l$是偶数,则只有按原来的顺序组成一个轮换一个插法;否则如果$l$是奇数,则它可以自己gay住自己(比如"1,2,3,4,5"可以变成"1,4,2,5,3"),有两种插法。所以,对每种长度的环,记录有多少个这种环,然后按上面几种组合方式统计一下答案就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 200010
#define LL long long
using namespace std;

const LL P=1000000007;

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN];

int n;
int g[MAXN],nume;
int p[MAXN];
bool visit0[MAXN],visit[MAXN];
int b[MAXN],l[MAXN],sl[MAXN],numb;
int cnt[MAXN];
LL f[MAXN],fac[MAXN],invfac[MAXN];
LL ans=1;

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

int dfs(int x){
    visit[x]=1;
    int numch=0;
    int res=0;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            numch++;
            res=dfs(e[i].to)+1;
        }
    if(numch>=2) ans=0;
    return res;
}

void gao(int x){
    numb=0;
    while(!visit[x]){
        visit[x]=1;
        b[++numb]=x;
        x=p[x];
    }
    int pos=0;
    for(int i=1;i<=numb;i++){
        l[i]=dfs(b[i]);
        if(l[i]) pos=i;
    }
    if(!pos){
        cnt[numb]++;
        return;
    }
    for(int i=1;i<=numb;i++){
        b[i+numb]=b[i];
        l[i+numb]=l[i];
        b[i]=b[i+pos-1];
        l[i]=l[i+pos-1];
    }
    for(int i=1;i<=numb;i++) sl[i]=sl[i-1]+l[i];
    LL res1=0,res2=0;
    if(sl[numb]-sl[numb-(l[1]-1)]==0){
        res1=1;
        for(int i=2;i<=numb;i++){
            if(!l[i]) continue;
            LL temp=0;
            if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
            if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
            res1=res1*temp%P;
        }
    }
    if(sl[numb]-sl[numb-l[1]]==0){
        res2=1;
        for(int i=2;i<=numb;i++){
            if(!l[i]) continue;
            LL temp=0;
            if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
            if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
            res2=res2*temp%P;
        }
    }
    ans=ans*(res1+res2)%P;
}

void init(){
    f[0]=1;
    for(int i=2;i<=n;i++) f[i]=f[i-2]*(i-1)%P;
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
    invfac[n]=getPow(fac[n],P-2);
    for(int i=n-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%P;
}

LL getC(int x,int y){
    return fac[x]*invfac[y]%P*invfac[x-y]%P;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",p+i);
        addEdge(p[i],i);
    }
    for(int i=1;i<=n;i++)
        if(!visit[i]){
            int x=i;
            for(;!visit0[x];x=p[x]) visit0[x]=1;
            gao(x);
        }
    init();
    for(int i=1;i<=n;i++)
        if(cnt[i]){
            LL res=0;
            for(int j=0;j<=cnt[i];j+=2)
                if(i>=3 && (i&1)) res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2)%P*getPow(2,cnt[i]-j))%P;
                else res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2))%P;
            ans=ans*res%P%P;
        }
    printf("%lld\n",ans);
    return 0;
}

查看详细内容