結果

問題 No.310 2文字しりとり
ユーザー Mi_SawaMi_Sawa
提出日時 2015-12-25 06:11:01
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,684 bytes
コンパイル時間 1,728 ms
コンパイル使用メモリ 177,180 KB
実行使用メモリ 260,896 KB
最終ジャッジ日時 2024-09-18 23:43:19
合計ジャッジ時間 9,849 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 WA -
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 19 ms
5,376 KB
testcase_19 AC 8 ms
5,376 KB
testcase_20 AC 19 ms
5,376 KB
testcase_21 TLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}

const int MOD = (int)(1E9+7);
struct MOD_INT{//{{{
    int x;
    MOD_INT(const int& x=0): x((x%MOD+MOD)%MOD){}
    MOD_INT(const ll& x): x((x%MOD+MOD)%MOD){}
    MOD_INT(const MOD_INT& o): x(o.x){}
    operator int(){return x;}
    MOD_INT pow(int e){
        MOD_INT res(1), b(*this);
        for(; e; e>>=1, b=b*b) if(e&1) res = res * b;
        return res;
    }
    MOD_INT inv(){ return pow(MOD-2); }
    template<class T> MOD_INT operator+(T o){return MOD_INT(x+MOD_INT(o).x);}
    template<class T> MOD_INT operator-(T o){return MOD_INT(x-MOD_INT(o).x);}
    template<class T> MOD_INT operator*(T o){return MOD_INT(((ll)x*MOD_INT(o).x));}
    template<class T> MOD_INT operator/(T o){return *this*MOD_INT(o).inv();}

    friend ostream &operator<<(ostream &os, const MOD_INT &x){
        return os << x.x;
    }

    static unsigned int xor128(){//{{{
        //static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
        static unsigned int x=129042, y=38923212, z=3829312, w=3893189;
        unsigned int t=x^(x<<11);
        x=y;y=z;z=w;
        return w=(w^(w>>19))^(t^(t>>8));
    }//}}}
    static int rnd(int m){ return xor128() % m; }
    static MOD_INT nonzero_random(){ return rnd(MOD-1)+1; }
};
#define DEFOP(OP, OPEQ) \
template<class T> MOD_INT& operator OPEQ(MOD_INT& a, T o){return a=a OP o;}\
template<class T> MOD_INT operator OP(T a, MOD_INT b){return MOD_INT(a).operator OP(b);}
DEFOP(+, +=); DEFOP(-, -=); DEFOP(*, *=); DEFOP(/, /=);
#undef DEFOP
//}}}
typedef MOD_INT mi;

// 最小多項式を求める
// sum_i res[i] * s[n+i] = 0 for all n
// 次数の上限を n として, 2n 以上の要素があればよい.
template<class F> vector<F> berlekamp_massey(const vector<F> &s){//{{{
    vector<F> C = {F(1)}, B = C;

    int m = 1;
    F b = 1;
    for(int n = 0; n < s.size(); ++n, ++m){
        const int L = C.size() - 1;
        F d = 0;
        for(int i = 0; i <= L; ++i) d += C[i] * s[n-i];
        if(d == F(0)) continue;
        const F t = - d / b;
        if(2 * L <= n){
            B.resize(max(C.size(), B.size() + m));
            for(int i = B.size()-1; i >= m; --i)
                B[i] = (i <= L ? C[i] + t * B[i-m] : t * B[i-m]);
            for(int i = 0; i < m; ++i) B[i] = (i <= L ? C[i] : F(0));

            B.swap(C);
            b = d;
            m = 0;
        }else{
            C.resize(max(C.size(), B.size() + m));
            for(int i = 0; i < B.size(); ++i) C[i + m] += t * B[i];
        }
    }
    reverse(begin(C), end(C));
    return C;
}//}}}

// ベクトルの列
template<class F> vector<F> berlekamp_massey(const vector<vector<F>> &vs){//{{{
    const int m = vs[0].size();
    vector<F> u(m);
    for(auto &x : u) x = F::nonzero_random();
    vector<F> s(vs.size());
    for(int i = 0; i < s.size(); ++i)
        s[i] = inner_product(begin(u), end(u), begin(vs[i]), F(0));
    return berlekamp_massey(s);
}//}}}

// 線型変換の最小多項式
template<class F, class LM = function<vector<F>(const vector<F> &)>> vector<F> min_polynomial(const int n, const LM f){//{{{
    vector<vector<F>> vs(2 * n + 1, vector<F>(n));
    for(auto &x : vs[0]) x = F::nonzero_random();
    for(int i = 1; i < vs.size(); ++i) vs[i] = f(vs[i-1]);
    return berlekamp_massey(vs);
}//}}}

// 行列の最小多項式(特性多項式ではない)
template<class F> vector<F> min_polynomial(const vector<vector<F>> &A){//{{{
    const int n = A.size();
    return min_polynomial<F>(A.size(), [&](const vector<F> &v){
        vector<F> res(n);
        for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
            res[i] += A[i][j] * v[j];
        return res; });
}//}}}

// 線型変換の determinant
template<class F, class LM = function<vector<F>(const vector<F> &)>> F determinant(const int n, const LM f){//{{{
    vector<F> d(n);
    int cnt = 1;
    for(auto &x : d) x = F::nonzero_random();
    auto p = min_polynomial<F>(n, [&](vector<F> v){
        for(int i = 0; i < n; ++i) v[i] = v[i] * d[i];
        return f(v); });
    if(p[0] == F(0)) return 0;
    F prod = 1;
    if(n%2) prod = -prod;
    for(auto &x : d) prod = prod * x;
    return p[0] / prod;
}//}}}

// 行列の determinant
template<class F> F determinant(const vector<vector<F>> &A){//{{{
    const int n = A.size();
    return determinant<F>(A.size(), [&](const vector<F> &v){
        vector<F> res(n);
        for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
            res[i] += A[i][j] * v[j];
        return res; });
}//}}}

bool solve(){
    using F = mi;
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n+1, vector<int>(n+1, 1));
    rep(i, n+1) g[i][n] = g[n][i] = 0;
    rep(_, m){
        int a, b; cin >> a >> b; --a; --b;
        g[a][b] = 0;
    }
    if(n * n == m){
        cout << 1 << endl; return true;
    }
    vector<int> ideg(n+1), odeg(n+1);
    rep(i, n) rep(j, n) if(g[i][j]){
        ++ideg[j]; ++odeg[i];
    }
    int s = -1, t = -1;
    rep(i, n) if(ideg[i] != odeg[i]){
        if(abs(ideg[i] - odeg[i]) > 1){
            cout << 0 << endl;
            return 0;
        }
        if(ideg[i] < odeg[i]){
            if(t != -1){ cout << 0 << endl; return 0; }
            t = i;
        }else{
            if(s != -1){ cout << 0 << endl; return 0; }
            s = i;
        }
    }
    if(s != -1){
        g[s][n] = g[n][t] = 1;
        ++ideg[t]; ++odeg[s];
        ideg[n] = odeg[n] = 1;
        ++n;
    }

    vector<vector<F>> Q(n-1, vector<F>(n-1, 0));
    rep(i, n-1) rep(j, n-1)
        Q[i][j] = (i == j ? odeg[i] - g[i][i] : - g[i][j]);

    vector<F> factorial(n+1, 1);
    rep(i, n) factorial[i+1] = factorial[i] * F(i+1);
    F ec = determinant(Q);
    rep(i, n) ec *= factorial[ideg[i] - 1];
    if(s == -1) ec *= n * n - m;

    cout << ec << endl;
    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:
0