Codeforces #184 Div2 D 「Olya and Graph」
問題
http://codeforces.com/contest/305/problem/D
訳
オリヤはn個の頂点とm個の辺を持つ、方向があり、重みなしのグラフを持っていた。いくつかの規則を守り、グラフの1番からn番への頂点を移動する事を考える。現在のグラフは辺を辿って、v -> uへと移動できなたらば、それはv < uとなっている。
今、オリヤは、好きなだけ辺の追加することによって(追加しなくても良い)以下のような性質を持つグラフにするのに、何通りの追加の仕方があるかを知りたい。
1. 頂点iから頂点i+1, i+2, ... nへたどり着くことが可能である。 2. 頂点vから頂点uへと到達可能であれば、v < uとなっていること。 3. 2つの頂点間では、辺の数は多くとも1つであること。 4. 頂点iから頂点jへの最短距離はj - i <= kのとき、j - iであること。 5. 頂点iから頂点jへの最短距離はj - i > kのとき、j - iもしくはj - i - kであること。
2つのグラフにおいて、ある辺を片方が持っていたがもう一方がもっていなかった場合、それは違う追加の仕方であるとみなす。
上記のルールを守る、辺の追加の仕方の数を出力せよ。
制約
1 <= n <= 10^6
1 <= m <= 10^5
1 <= k <= 10^6
Editorialsを見て
あとで
ソースコード
const int MOD = 1000000007; int degs[1000050]; bool use[1000050]; int add( int a, int b ){ a += b; if( a >= MOD ) a -= MOD; return a; } int main() { int n, m, k; scanf( "%d %d %d", &n, &m, &k ); // degs初期化 degs[0] = 1; for( int i = 1; i <= n; i++ ){ degs[i] = add( degs[i-1], degs[i-1] ); } // エッジ入力 vector< int > edges; // edges[i] : 頂点iから頂点i+k+1へのエッジ memset( use, false, sizeof(use) ); // use[i] : 頂点iから頂点i+k+1への辺があるか for( int i = 0; i < m; i++ ){ int u, v; scanf( "%d %d", &u, &v ); // 一つ進むだけの辺 if( v - u == 1 ) continue; // i->i+k+1以外に辺が付いてたらダメ if( v - u != k + 1 ){ cout << 0 << endl; return 0; } // 辺を追加 edges.push_back( u ); use[u] = true; } m = edges.size(); // 2回以上辺を通れてしまわないかチェック for( int i = 1; i < m; i++ ){ if( !(edges[i] < edges[0] + k + 1) ){ cout << 0 << endl; return 0; } } // 辺を置ける範囲を取得 int start = 1; int end = n - k - 1; if( m != 0 ){ start = max( start, edges[m-1] - k ); end = min( end, edges[0] + k ); } // 頂点を前から見ていき、答えを出す int ans = 0; int e = m; // 範囲中に含む辺の数 for( int v = start; v <= end; v++ ){ // この頂点は既に張られている if( use[v] ){ e--; }else{ // この頂点に張ったときの場合の数を数える int cnt = min( end, min( n - k - 1, v + k )) - v - e; ans = add( ans, degs[cnt] ); } } ans++; // まったく辺を張らない場合 cout << ans << endl; return 0; }