結果

問題 No.310 2文字しりとり
ユーザー skylee
提出日時 2018-12-21 11:21:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,329 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 38,500 KB
実行使用メモリ 70,764 KB
最終ジャッジ日時 2024-09-25 09:20:09
合計ジャッジ時間 8,525 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=4001,mod=1e9+7;
int mat[N][N],fac[N],node[N],in[N],out[N];
inline void exgcd(const int &a,const int &b,int &x,int &y) {
    if(!b) {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
inline int inv(const int &x) {
    int ret,tmp;
    exgcd(x,mod,ret,tmp);
    return (ret%mod+mod)%mod;
}
inline void fail() {
    puts("0");
    exit(0);
}
inline int matrix_tree(const int &n) {
    for(register int i=1;i<=n;i++) {
        for(register int j=1;j<=n;j++) {
            mat[i][j]=(mat[i][j]%mod+mod)%mod;
        }
    }
    int ret=1;
    for(register int i=1;i<=n;i++) {
        int p=0;
        for(register int j=i;j<=n;j++) {
            if(mat[i][j]) p=j;
        }
        if(!p) return 0;
        if(i!=p) {
            ret=(mod-ret)%mod;
            for(register int j=1;j<=n;j++) {
                std::swap(mat[j][i],mat[j][p]);
            }
        }
        ret=1ll*ret*mat[i][i]%mod;
        const int t=inv(mat[i][i]);
        for(register int j=i;j<=n;j++) {
            mat[i][j]=1ll*mat[i][j]*t%mod;
        }
        for(register int j=i+1;j<=n;j++) {
            if(mat[j][i]==0) continue;
            const int t=mat[j][i];
            for(register int k=i;k<=n;k++) {
                (mat[j][k]-=1ll*mat[i][k]*t%mod)%=mod;
            }
        }
    }
    return ret;
}
int main() {
    const int n=getint(),m=getint();
    for(register int i=fac[0]=1;i<=n;i++) {
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    for(register int i=1;i<=n;i++) {
        in[i]=out[i]=mat[i][i]=n;
        for(register int j=1;j<=n;j++) {
            mat[i][j]--;
        }
    }
    for(register int i=0;i<m;i++) {
        const int x=getint(),y=getint();
        in[y]--;
        out[x]--;
        mat[x][y]++;
        mat[y][y]--;
    }
    int st=-1,en=-1,x=0;
    for(register int i=1;i<=n;i++) {
        if(in[i]==0&&out[i]==0) continue;
        node[++x]=i;
        if(std::abs(in[i]-out[i])>1) fail();
        if(out[i]==in[i]+1) {
            if(st!=-1) fail();
            st=i;
        }
        if(out[i]==in[i]-1) {
            if(en!=-1) fail();
            en=i;
        }
    }
    if(x==0||x==1) {
        puts("1");
        return 0;
    }
    int ans=1;
    if(st!=-1&&en!=-1) {
        in[st]++;
        out[en]++;
        mat[en][st]--;
        mat[st][st]++;
    } else {
        ans=n*n-m;
    }
    for(register int i=1;i<=x;i++) {
        mat[i][i]=mat[node[i]][node[i]];
    }
    for(register int i=1;i<=x;i++) {
        ans=1ll*ans*fac[out[node[i]]-1]%mod;
    }
    ans=1ll*ans*matrix_tree(x-1)%mod;
    printf("%d\n",ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0