先%一发达哥

T1,其实不难,就是一个简单的dp+矩阵快速幂加个原根优化,其实是模意义之前没做过题,有点懵,一开始思路也光想数学了,就gg了……

模意义下所有运算都和正常运算一样,只是除变成了乘逆元!!

定义状态数组f[i][j]表示第i步转移后模数为j的概率,矩阵乘优化,可得80分,正解是把每个数转化为p原根的i次方,别的都一样,会发现这样出来的是循环矩阵,复杂度降为O(logm*mod^2)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define mod 1000000007#define N 1005using namespace std;LL n,m,p,nn;LL f[N],g[N],h[N],D[N],ans,pp[N],id[N],num[N];LL qp(LL a,LL b){    LL ans=1;    while(b){        if(b&1)ans=ans*a%mod;        a=a*a%mod;b>>=1;    }    return ans;}bool bo[N];int find(int x){    for(int i=2;i<=x;i++){        memset(bo,0,sizeof bo);        int tim=0,now=1;        while(tim
          
           >=1; } mp(f,h,h); for(int i=0;i
          
         
        
       
      
     

T2:0的情况我们可以先暴力计算出b[1],然后从b[1]出发开始dfs，由某个点的父亲的b[i]推出这个点的b[i],变化的是这个点和父亲的连边的贡献,也就是这条边两侧的点的a[i]之和的差值.

1的情况就稍微复杂一点.设以x为根的子树中所有a[i]之和为sum(x)，S=∑ni=1a[i]，由0的情况可知f[x]=b[x]-b[fa[x]]=S-2*sum[x];dfs一遍可以得到n-1个式子，又b[root]=∑ni=1sum[i]，所以

S=∑ni=1f[i]+2∗b[root]n−1

最后再来一遍dfs就好了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 100050using namespace std;int T,n,opt;int e=1,head[N];int fa[N],sum[N],b[N],a[N],f[N];long long all;struct edge{    int u,v,next;}ed[2*N];void add(int u,int v){    ed[e].u=u;ed[e].v=v;    ed[e].next=head[u];    head[u]=e++;}void dfs1(int x){    sum[x]+=a[x];    for(int i=head[x];i;i=ed[i].next){        int v=ed[i].v;        if(v==fa[x])continue;        fa[v]=x;        dfs1(v);        sum[x]+=sum[v];b[x]+=sum[v]+b[v];    }}void dfs2(int x){    for(int i=head[x];i;i=ed[i].next){        int v=ed[i].v;        if(v==fa[x])continue;        b[v]=b[x]-sum[v]+(all-sum[v]);        dfs2(v);    }}void dfs3(int x){    f[x]=b[x]-b[fa[x]];//f[x]=all-2*sum[x]    for(int i=head[x];i;i=ed[i].next){        int v=ed[i].v;        if(v==fa[x])continue;        fa[v]=x; dfs3(v);    }}void dfs4(int x){    if(x==1)sum[x]=all;    else sum[x]=(all-f[x])/2;    a[x]=sum[x];    for(int i=head[x];i;i=ed[i].next){        int v=ed[i].v;        if(v==fa[x])continue;        dfs4(v);        a[x]-=sum[v];    }}void init(){    e=1;all=0;    memset(head,0,sizeof head);    memset(fa,0,sizeof fa);    memset(sum,0,sizeof sum);    memset(a,0,sizeof a);    memset(b,0,sizeof b);    memset(f,0,sizeof f);}int main(){    scanf("%d",&T);    while(T--){        init();        scanf("%d",&n); int u,v;        for(int i=1;i
         
        
       
      
     

T3,组合数，卡特兰数，dp杂糅

opt=0:枚举横向移动了多少步.横向移动i步时方案数为

Cin∗Ci/2i∗C(n−i)/2n−1

opt=1:纯卡特兰数

opt=2:f[i]表示走了i步回到原点的方案数,枚举第一次回到原点时走过的步数j,则此时方案数为4∗f[i−j]∗catalan(j/2−1)(减1是为了保证没有第一步就走回来)

opt=3:依然枚举横向移动了多少步.横向移动i步时,方案数为

Cin∗catalan(i/2)∗catalan((n−i)/2)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define mod 1000000007#define N 100050#define LL long longusing namespace std;LL fac[2*N],ans,now,f[1050];int n,opt;LL qp(LL a,LL b){    LL ans=1;    while(b){        if(b&1)ans=ans*a%mod;        a=a*a%mod;b>>=1;    }    return ans;}LL C(int a,int b){    if(!b||b==a)return 1;    if(b>a)return 0;    return (fac[a]*qp(fac[a-b],mod-2)%mod)*qp(fac[b],mod-2)%mod;}LL cal(int x){    if(x<=0)return 1;    return C(2*x,x)*qp(x+1,mod-2)%mod;}int main(){    scanf("%d%d",&n,&opt);    if(n&1){
    printf("0\n");return 0;}    fac[1]=1;    for(int i=2;i<=2*n;i++)fac[i]=fac[i-1]*i%mod;    if(opt==0){        for(int i=0;i<=n;i+=2){            now=(C(n,i)*C(i,i>>1)%mod)*C((n-i),(n-i)>>1)%mod;            ans=(ans+now)%mod;        }        printf("%lld\n",ans);        return 0;    }    if(opt==1){        ans=cal(n>>1);        printf("%lld\n",ans);    }    if(opt==2){        f[0]=1;        for(int i=2;i<=n;i+=2)            for(int j=0;j<=i;j+=2)                f[i]=(f[i]+4*f[i-j]*cal((j>>1)-1))%mod;        printf("%lld\n",f[n]);    }    if(opt==3){        for(int i=0;i<=n;i+=2){            now=C(n,i)*cal(i>>1)%mod*cal((n-i)>>1)%mod;            ans=(ans+now)%mod;        }        printf("%lld\n",ans);    }    return 0;}
         
        
       
      
     

再贴个考试时65分的傻暴力

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define mod 1000000007using namespace std;int n,opt;long long f[2][2050][2050];int main(){    scanf("%d%d",&n,&opt);    if(n&1){        printf("0\n");        return 0;    }    if(opt==0){        int ii=0;        f[ii][n+1][n+1]=1;        for(int i=1;i<=n;i++){            ii^=1;            for(int j=1;j<=2*n+2;j++)                for(int k=1;k<=2*n+2;k++)                    if(f[ii^1][j][k]){                        f[ii][j+1][k]=(f[ii][j+1][k]+f[ii^1][j][k])%mod;                        f[ii][j-1][k]=(f[ii][j-1][k]+f[ii^1][j][k])%mod;                        f[ii][j][k+1]=(f[ii][j][k+1]+f[ii^1][j][k])%mod;                        f[ii][j][k-1]=(f[ii][j][k-1]+f[ii^1][j][k])%mod;                        f[ii^1][j][k]=0;                    }        }        printf("%lld\n",f[ii][n+1][n+1]);    }    if(opt==1){        int ii=0;        f[ii][n+1][n+1]=1;        for(int i=1;i<=n;i++){            ii^=1;            for(int j=n;j<=2*n+2;j++)                for(int k=n+1;k
          
           =n+1) f[ii][j-1][k]=(f[ii][j-1][k]+f[ii^1][j][k])%mod; f[ii^1][j][k]=0; } } printf("%lld\n",f[ii][n+1][n+1]); } if(opt==2){ int ii=0; f[ii][n+1][n+1]=1; for(int i=1;i<=n;i++){ ii^=1; for(int j=1;j<=2*n+2;j++) for(int k=n+1;k