ZJT's Blog

大変に気分がいい~

集训队作业之ARC062-F

2017-10-23 16:122017-10-23 16:13
集训队作业AtCoderPolya定理打表Tarjan

传送门

有个神秘的结论就是任意一个边数大于点数的点双连通分量里面,可以通过循环移位的组合来得到点双里面的边的任意置换。这个结论是我卡了2h不会做之后打表打出来的。。。

然后就好做了,直接把点双求出来之后,如果一条边不属于任意一个点双,则他对答案的贡献(乘上去)就是$K$。然后考虑每个点双,记这个点双里面有$d$条边,如果这个点双里面没有环(孤立点或两个点之间一条边),贡献就是$K^d$;如果这个点双是一个环,则置换群比较规律,直接暴力用polya定理算出贡献就行了;否则,根据上面那个结论,边的顺序可以随便交换,所以贡献就是用不同的颜色划分边集的方案数,即$\binom{d+K-1}{K-1}$。

顺便讲个笑话,之前我和hgr,gjs他们看到一道题,就是把上面最后一种情况单独出出来了,$d,K\leq 10^5$。然后我们一直在套polya定理做,最后得出来一个含有第一类斯特林数的式子,差点就开始写第一类斯特林数求行了。结果发现别人AC代码才几百B,觉得有点不对劲,发现那整个斯特林数的式子能直接化成一个组合数(就是上面那个)。。。这个的印象还是很深刻的,所以今天做这题就没有陷进polya定理和斯特林数的深坑里去了2333

#include <cstdio>
#include <cstring>
#include <stack>
#define LL long long
#define MAXN 2010
using namespace std;

const LL P=1000000007;

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

int n,m,C;
int g[MAXN],nume;
int dfn[MAXN],low[MAXN],numw;
stack<int> S;
bool instack[MAXN];
int c[MAXN][MAXN],d[MAXN],d0[MAXN],numc;
LL binom[MAXN][MAXN];

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

void tarjan(int x,int pe){
    dfn[x]=low[x]=++numw;
    S.push(x);
    instack[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(i^pe){
            if(!dfn[e[i].to]){
                tarjan(e[i].to,i^1);
                if(low[e[i].to]<low[x]) low[x]=low[e[i].to];
                if(low[e[i].to]>=dfn[x]){
                    numc++;
                    while(S.top()!=e[i].to){
                        c[S.top()][numc]=1;
                        instack[S.top()]=0;
                        d0[numc]++;
                        S.pop();
                    }
                    c[e[i].to][numc]=1;
                    instack[e[i].to]=0;
                    c[x][numc]=1;
                    d0[numc]+=2;
                    S.pop();
                }
            }else if(instack[e[i].to] && dfn[e[i].to]<low[x]) low[x]=dfn[e[i].to];
        }
}

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;
}

int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}

LL calc(int x){
    LL res=0;
    for(int i=0;i<x;i++)
        res=(res+getPow(C,gcd(i,x)))%P;
    res=res*getPow(x,P-2)%P;
    return res;
}

LL calc2(int x){
    return binom[C+x-1][C-1];
}

void init(){
    for(int i=0;i<MAXN;i++){
        binom[i][0]=1;
        for(int j=1;j<=i;j++)
            binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%P;
    }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    init();
    memset(g,-1,sizeof g);
    scanf("%d%d%d",&n,&m,&C);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            tarjan(i,-1);
            numc++;
            while(!S.empty()){
                c[S.top()][numc]=1;
                d0[numc]++;
                instack[S.top()]=0;
                S.pop();
            }
        }
    LL ans=1;
    for(int x=1;x<=n;x++)
        for(int i=g[x];~i;i=e[i].next)
            if(i&1){
                bool flag=0;
                for(int j=1;j<=numc;j++)
                    if(c[x][j] && c[e[i].to][j]){
                        d[j]++;
                        flag=1;
                        break;
                    }
                if(!flag) ans=ans*C%P;
            }
    for(int i=1;i<=numc;i++){
        if(d0[i]==1) continue;
        if(d[i]==d0[i]) ans=ans*calc(d0[i])%P;
        else if(d[i]==d0[i]-1) ans=ans*getPow(C,d[i])%P;
        else ans=ans*calc2(d[i])%P;
    }
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之AGC006-C

2017-9-24 9:262017-11-2 11:35
集训队作业AtCoder打表差分

传送门

推了一下发现其实就是每次把一个数换成相邻两个数的和减掉这个数。把每个位置表示成其他位置的线性变换后,打了个表看看有什么规律,发现两行之间好像差别不大?于是想到了差分。差分后,在第$x$位做一个这样的操作,等价于把$x$和$x+1$位的值互换。这样我们直接把$M$次操作看成是$M$个对换,做完这些操作就可以看成是$1$到$n$的一个置换。我们我们直接把置换拆成一些轮换,然后直接在每个轮换上面每个点走$K$步就行啦。

(顺便不知道浮点意义何在。。。可能是用来坑人的)

代码:

#include <cstdio>
#include <cstring>
#define MAXN 100010
#define LL long long

int n,m;
LL v[MAXN],ans[MAXN],K;
int a[MAXN];
int p[MAXN];
bool visit[MAXN];

void gao(int x){
    static int b[MAXN];
    int numb=0;
    b[numb++]=x;
    visit[x]=1;
    for(int i=a[x];i^x;i=a[i]){
        b[numb++]=i;
        visit[i]=1;
    }
    for(int i=0;i<numb;i++){
        int x=b[i];
        p[x]=b[(K+i)%numb];
    }
}

int main(){
#ifdef DEBUG
    freopen("C.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",v+i),a[i]=i;
    for(int i=n;i>=2;i--) v[i]-=v[i-1];
    scanf("%d%lld",&m,&K);
    while(m--){
        int t;
        scanf("%d",&t);
        a[t]^=a[t+1]^=a[t]^=a[t+1];
    }
    for(int i=1;i<=n;i++)
        if(!visit[i])
            gao(i);
    for(int i=1;i<=n;i++)
        ans[i]=v[p[i]];
    for(int i=2;i<=n;i++)
        ans[i]+=ans[i-1];
    for(int i=1;i<=n;i++) printf("%.1lf\n",(double)ans[i]);
}

查看详细内容