Codeforces Round #184 (Div. 2) D. Olya and Graph
誤読してしまった。最短路の長さの条件を、最短路となる道の数の条件と勘違いした。とてもつらい。
D. Olya and Graph
問題
頂点のindexがtopological sortされたDAG $G$と、整数$k$が与えられる。 $G$にいくつかの辺を加える。 以下の条件を満たすような辺の追加の仕方の数を答えよ。
- DAGでありtopological sort済みという条件を保つ。
- 多重辺は禁止。
- 任意の頂点$u, v$($u \lt v$)に関して、$u$から$v$への道が存在し、その最短路の長さは$v - u$か$v - u - k$に一致する。
解法
頂点$i$から$i+1$へは必ず辺が必要なので、これを全て張る。 他に辺がないとすると、頂点$u,v$間の最短路の長さは全て$v - u$になる。
頂点$u,v$間の最短路の長さは$v - u - k$でもよいので、頂点$i$から$i+k+1$へshortcut辺を張ってもよい。 逆にこれら以外の辺がひとつでも存在すれば、条件を満たさない。
また、頂点$u,v$で、その最短路中でこのshortcutの辺を複数回使用するようなことがあれば、これは条件を満たさない。 つまりshortcut辺のsourceになっている頂点のindexを$i$とすると、shortcut辺のsourceになれる頂点は$i, i+1, \dots, i+k$のみである。
以上をもとに計算すればよい。
実装
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
constexpr ll mod = 1000000007;
ll powll(ll x, int y) {
ll z = 1;
for (int i = 0; (1 << i) <= y; ++ i) {
if (y & (1 << i)) {
z = (z * x) % mod;
}
x = (x * x) % mod;
}
return z;
}
int main() {
int n, m, k; cin >> n >> m >> k;
vector<int> u(m), v(m);
repeat (i,m) {
cin >> u[i] >> v[i];
-- u[i]; -- v[i];
}
bool is_valid = true;
vector<bool> has_shortcut(n);
int leftmost_shortcut = 1000000007;
int rightmost_shortcut = -1;
repeat (i,m) {
if (v[i] - u[i] == 1) {
// nop
} else if (v[i] - u[i] == k+1) {
has_shortcut[u[i]] = true;
leftmost_shortcut = min( leftmost_shortcut, u[i]);
rightmost_shortcut = max(rightmost_shortcut, u[i]);
} else {
is_valid = false;
break;
}
}
if (leftmost_shortcut + k+1 <= rightmost_shortcut) {
is_valid = false;
}
vector<int> acc_shortcut(n+1);
repeat (i,n) acc_shortcut[i+1] = acc_shortcut[i] + has_shortcut[i];
ll result = 0;
if (not is_valid) {
// nop
} else {
result += 1;
repeat (i,n) {
if (i + k+1 < n) {
if (i <= leftmost_shortcut and rightmost_shortcut < i + k+1) {
int j = min(k, n - (i + k+1) - 1) - (acc_shortcut[i+k+1] - acc_shortcut[i+1]);
result = (result + powll(2, j) - has_shortcut[i]) % mod;
}
}
}
}
cout << result << endl;
return 0;
}