鲜花.cpp

昨天 T2 求调捏qwq

得分 \(55\)，分别在 #3，#5，#7 wa 了。

//transport
#include<bits/stdc++.h>
#define N 1010
#define M 4010
using namespace std;
const long long mod=1e9+7;

long long qpow(long long base,int power){
    long long ans=1;
    for(;power;power>>=1,base=(base*base)%mod)
        if(power&1) ans=ans*base%mod;
    return ans;
}

int c[M],si[M];
long long f[M][M],g[M][M],w[M][M];
int path[N][N],d[N][N];
int cnt[M];
int to[M][2];
int siz[N];
bool vis[M];

struct edges{
    int s,e,nex,id;
    bool vi;
}ed[N<<1];
int pre[N],ti=1;

inline void add(int s,int e,int id){
    ed[++ti]={s,e,pre[s],id,0};
    pre[s]=ti;
    return;
}

void dfs_a(int x,int fa){
    siz[x]=1;
    for(int i=pre[x];i;i=ed[i].nex){
        if(ed[i].e==fa||ed[i].vi) continue;
        dfs_a(ed[i].e,x);
        siz[x]+=siz[ed[i].e];
    }
    return;
}

void dfs_b(int x,int fa,int S,int &ans){
    for(int i=pre[x];i;i=ed[i].nex){
        if(ed[i].e==fa||ed[i].vi) continue;
        if((S-siz[ed[i].e])*siz[ed[i].e]==cnt[ed[i].id]) ans=i;
        dfs_b(ed[i].e,x,S,ans);
    }
    return;
}

int init(int rt){
    dfs_a(rt,0);
    int ans=0;
    dfs_b(rt,0,siz[rt],ans);
    int s=ed[ans].s,e=ed[ans].e,x=ed[ans].id;
    si[x]=siz[rt];
    c[x]+=siz[rt]-1;
    if(siz[s]<siz[e]) swap(s,e);
    ed[ans].vi=1;
    ed[ans^1].vi=1;
    if(siz[rt]-siz[e]-1) to[x][0]=init(s);
    if(siz[e]-1) to[x][1]=init(e);
    c[x]+=c[to[x][0]]-si[to[x][0]]+1;
    c[x]+=c[to[x][1]]-si[to[x][1]]+1;
    return x;
}

long long fac[M],inv[M];

void inits(int m){
    fac[0]=1;
    for(int i=1;i<=m;i++) fac[i]=(fac[i-1]*i)%mod;
    inv[m]=qpow(fac[m],mod-2);
    for(int i=m-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    si[0]=1;
    c[0]=0;
    f[0][0]=1;
    g[0][0]=1;
    return;
}

inline long long C(int n,int m){
    if(m>n) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

void solve(int rt){
    int x=to[rt][0],y=to[rt][1];
    if(x) solve(x);
    if(y) solve(y);
    int a=c[x]-si[x]+1,b=c[y]-si[y]+1;
    for(int i=0;i<=a;i++)
        for(int j=0;j<=b;j++)
            w[rt][i+j]=C(i+j,i)*C(c[x]-i+c[y]-j,c[x]-i)%mod*g[x][i]%mod*g[y][j]%mod;
    int k=c[rt]-c[x]-c[y]-1;
    for(int i=0;i<=a+b;i++) f[rt][i+k]=w[rt][i]*fac[k]%mod*C(k+i,i)%mod;
    for(int i=a+b+k;i>=0;i--) g[rt][i]=(g[rt][i+1]+f[rt][i])%mod;
    return;
}

int main(){
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
        for(int j=1,ds;j<i;j++){
            scanf("%d",&ds);
            d[i][j]=ds;
            d[j][i]=ds;
            cnt[ds]++;
            vis[ds]=1;
        }
    for(int i=1,s,e;i<=m;i++){
        scanf("%d%d",&s,&e);
        path[s][e]=i;
        path[e][s]=i;
        if(d[s][e]!=i) c[d[s][e]]++;
        if(vis[i]){
            add(s,e,i);
            add(e,s,i);
        }
    }
    inits(m);
    int ma=init(1);
    solve(ma);
    printf("%lld",g[ma][0]);
}