Cptraser/ 三月 14, 2019/ 2019.3/ 0 comments

Codeforces660E

看出题中子序列长度一样则贡献一样,那么:

    \[\sum_{i=1}^n\sum_{j=i}^n m^i m^{n-j} {j-1\choose i-1} (m-1)^{j-i}\]

交换枚举顺序,发生了什么?

    \[\sum_{j=1}^n\sum_{i=1}^j m^i m^{n-j} {j-1\choose i-1} (m-1)^{j-i}\]

    \[\sum_{j=1}^n m^{n-j+1} \sum_{i=1}^{j} {j-1\choose i-1} m^{i-1} (m-1)^{j-i}\]

由二项式定理合并((x+y)^n=\sum_{i=0}^n {n\choose i} x^i y^{n-i}j-1\rightarrow n,i-1\rightarrow i,j-i\rightarrow n-i):

    \[\sum_{j=1}^n m^{n-j+1}(2m-1)^{j-1}\]

最后答案加上m^n

#include <cstdio>
using namespace std;

int N,M,Mod=1e9+7,Ans;
int Ksm(int x,int y){int res=1;for(;y;y>>=1,x=(long long)x*x%Mod)if(y&1)res=(long long)res*x%Mod;return res;
}
int main()
{
    scanf("%d%d",&N,&M),Ans=Ksm(M,N);
    for(int i=0;i<N;i++)
        Ans=(long long)(Ans+(long long)Ksm(M,N-i)*Ksm(M*2-1,i)%Mod)%Mod;
    printf("%d\n",Ans);
}

Codeforces632F

首先判断前两个条件是否满足。将原数组看做邻接矩阵,那么原数组就表示一个无向完全图。

f_{i,j}表示i\rightarrow j任意路径上最长边的最小值,那么a_{i,j}\geq f_{i,j}

a_{i,j}\leq max(a_{i,k},a_{k,j})得:a_{i,j}\leq max(a_{i,k1},a_{k1,j}),a_{k1,j}\leq max(a_{k1,k2},a_{k2,j})...a_{k_{m-1},j}\leq max(a_{k_m},a_j)

a_{i,j}\leq max(a_{i,k1},a_{k1,k2}...a_{k_m,a_j})=f_{i,j}a_{i,j}小于任何路径的max

f_{i,j}=a_{i,j}

那么先构建最小生成树,对于非树边判断连成的环上的点最大值是否等于a_{i,j}

由于这题范围小,直接枚举根dfs即可。

这道题其实还可以bitset卡常。对于每一行或列,按顺序记录每一个点的相对大小状态,对于一个点的行列状态,只有他们或在一起为全1时才是合法。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int Maxn=2505;

int N,Fa[Maxn],A[Maxn][Maxn],Cpt;
struct Edge{int x,y,c;}E[Maxn*Maxn>>1];
int Cmp(Edge x,Edge y){return x.c<y.c;}
int getf(int x){return x==Fa[x]?x:Fa[x]=getf(Fa[x]);}

int head[Maxn],to[Maxn<<1],nxt[Maxn<<1],w[Maxn<<1],Cnt;
void Add(int x,int y,int c){
    nxt[++Cnt]=head[x],to[Cnt]=y,w[head[x]=Cnt]=c;
    nxt[++Cnt]=head[y],to[Cnt]=x,w[head[y]=Cnt]=c;
}

bool dfs(int x,int fa,int rt,int val){
    if(A[rt][x]^val)return 1;int Opt=0;
    for(int i=head[x];i;i=nxt[i])if(to[i]^fa){
        Opt|=dfs(to[i],x,rt,max(val,w[i]));
    }return Opt;
}

int main()
{
    read(N);
    for(int i=1;i<=N;i++)Fa[i]=i;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)read(A[i][j]);
    for(int i=1;i<=N;i++)if(A[i][i])return puts("NOT MAGIC"),0;
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)if(A[i][j]^A[j][i])return puts("NOT MAGIC"),0;
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)E[++Cpt]=(Edge){i,j,A[i][j]};
    sort(E+1,E+Cpt+1,Cmp);
    for(int i=1;i<=Cpt;i++){
        int x=getf(E[i].x),y=getf(E[i].y);
        if(x^y)Fa[x]=y,Add(E[i].x,E[i].y,E[i].c);
    }
    for(int i=1;i<=N;i++)if(dfs(i,0,i,0))return puts("NOT MAGIC"),0;
    puts("MAGIC");
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*