Proficient.
Put your skills to the test.

Problem summary

A park is a straight-line planar undirected graph. A river is a polyline whose first and last segments extend to infinity; any edge intersecting it is a bridge. Count walks from vertex 1 back to vertex 1 that traverse exactly K bridge edges and have at most C consecutive ordinary edges, modulo 1234567891. Vertices and edges may be revisited.

Constraints

3 ≤ N ≤ 1000; 1 ≤ M ≤ N²; 1 ≤ K,C ≤ 1000; 2 ≤ B ≤ 10; coordinates are integers in [0,10000]. The graph is simple and planar with edges meeting only at shared endpoints. There are 1–10 bridge edges. All input points differ, and no three are collinear.

Worked example

An independently prepared example for this explanation.

5 6 2 2 3
3 0
2 3
0 2
2 5
1 5
1 2
3 1
2 3
4 5
3 5
4 2
5 7
0 6
1 3

9

Solution analysis

1. Classify each graph edge by exact cross products. Write each river piece as p+t(q−p), solve for the intersection parameters, and require the graph-edge parameter to lie strictly between 0 and 1. Interior pieces require 0<t<1; the first piece allows t<1 and the last allows t>0. When B=2 the river is the whole line. The no-three-collinear guarantee removes endpoint and overlap ambiguities. Mark an edge once even if it meets several river pieces.
2. Every valid walk splits uniquely into K directed bridge traversals separated by K+1 ordinary-edge walks of lengths between 0 and C. Only the entrance and bridge endpoints matter between these blocks: at most H=21 terminals. For each terminal s, run length-by-length walk DP on the graph after deleting bridges. Sum lengths 0 through C to obtain paths[s][t], the number of permissible ordinary blocks to each terminal t.
3. Start with one way at the entrance. To append a bridge a→b, multiply the ways currently at terminal s by paths[s][a], and add to the new ways at b. Repeat exactly K times. Finally multiply each terminal’s count by its ordinary-block count back to the entrance. Zero-length blocks allow consecutive bridge crossings, including immediately traversing the same bridge in reverse.
4. In the first sample, edges (1,3), (2,3), (3,5) are bridges. With K=2 and C=2, a direct out-and-back bridge crossing is allowed, as are walks with up to two ordinary edges before, between, and after crossings. Summing the unique block decompositions gives 9. The second official example gives 303923512.

Why it works

The geometric parameter conditions are exactly the intersection conditions for the specified segments, rays, or line, so the marked edges are precisely the bridges. Induction on ordinary-block length proves the first DP counts every ordinary walk of each length exactly once. Every complete walk has a unique split at its bridge traversals. Each compressed transition chooses exactly its next ordinary block and next directed bridge, so induction on the bridge count establishes that the second DP counts every prefix once. Appending the final ordinary block to vertex 1 yields exactly all valid closed walks.

Watch out. Apply the C limit before the first bridge and after the last as well. Include ordinary blocks of length zero. Treat a graph edge crossing the river several times as one bridge traversal, because bridges are edges. Avoid floating-point intersection tests and 32-bit modular products.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
const long long MOD=1234567891;
struct Point{
    long long x,y;
};
Point difference(Point a,Point b){
    return {a.x-b.x,a.y-b.y};
}
long long cross(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
// Intersect graph segment a--b with p+t(q-p); restrict t as requested.
bool crosses(Point a,Point b,Point p,Point q,int type){
    Point direction=difference(q,p);
    Point edge=difference(b,a);
    long long denominator=cross(direction,edge);
    long long numerator=cross(difference(a,p),edge);
    long long alongEdge=cross(difference(a,p),direction);
    if(denominator==0){
        return false;
    }
    if(denominator<0){
        denominator=-denominator;
        numerator=-numerator;
        alongEdge=-alongEdge;
    }
    if(alongEdge<=0||alongEdge>=denominator){
        return false;
    }
    if(type==0){
        return true; // B=2: the whole infinite line.
    }
    if(type==1){
        return numerator<denominator; // First segment extends backwards.
    }
    if(type==2){
        return numerator>0; // Last segment extends forwards.
    }
    return numerator>0&&numerator<denominator;
}
int main(){
    int n,m,k,limit,bends;
    cin>>n>>m>>k>>limit>>bends;
    vector<Point>vertex(n),river(bends);
    for(Point&p:vertex){
        cin>>p.x>>p.y;
    }
    vector<pair<int,int>>edges(m);
    for(auto&[a,b]:edges){
        cin>>a>>b;
        --a;
        --b;
    }
    for(Point&p:river){
        cin>>p.x>>p.y;
    }
    vector<pair<int,int>>ordinary,bridge;
    vector<int>terminals={0};
    for(auto[a,b]:edges){
        bool wet=false;
        for(int j=0;j+1<bends;j++){
            int type=bends==2?0:(j==0?1:(j==bends-2?2:3));
            wet=wet||crosses(vertex[a],vertex[b],river[j],river[j+1],type);
        }
        if(wet){
            bridge.push_back({a,b});
            bridge.push_back({b,a});
            terminals.push_back(a);
            terminals.push_back(b);
        }
        else{
            ordinary.push_back({a,b});
        }
    }
    sort(terminals.begin(),terminals.end());
    terminals.erase(unique(terminals.begin(),terminals.end()),terminals.end());
    int h=static_cast<int>(terminals.size());
    vector<int>index(n,-1);
    for(int i=0;i<h;i++){
        index[terminals[i]]=i;
    }
    vector<vector<long long>>paths(h,vector<long long>(h));
    for(int s=0;s<h;s++){
        vector<long long>current(n),next(n);
        current[terminals[s]]=1;
        for(int length=0;length<=limit;length++){
            for(int t=0;t<h;t++){
                paths[s][t]=(paths[s][t]+current[terminals[t]])%MOD;
            }
            if(length==limit){
                break;
            }
            fill(next.begin(),next.end(),0);
            for(auto[a,b]:ordinary){
                next[a]=(next[a]+current[b])%MOD;
                next[b]=(next[b]+current[a])%MOD;
            }
            current.swap(next);
        }
    }
    vector<long long>current(h),next(h);
    current[index[0]]=1;
    for(int used=0;used<k;used++){
        fill(next.begin(),next.end(),0);
        for(int s=0;s<h;s++){
            for(auto[a,b]:bridge){
                next[index[b]]=(next[index[b]]+current[s]*paths[s][index[a]])%MOD;
            }
        }
        current.swap(next);
    }
    long long answer=0;
    for(int s=0;s<h;s++){
        answer=(answer+current[s]*paths[s][index[0]])%MOD;
    }
    cout<<answer<<'\n';
}