結果
| 問題 |
No.310 2文字しりとり
|
| コンテスト | |
| ユーザー |
 Mi_Sawa
|
| 提出日時 | 2015-12-25 06:11:01 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 WA * 1 TLE * 1 -- * 6 |
ソースコード
#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: