[CC-CHEFGRPH]Time to Study Graphs with Chef

题目大意：

一个有向图可以分成\(n+2(n\le10^{12})\)层，第\(0\)层和第\(n+1\)层有\(1\)个点，剩下每一层\(m(m\le10^5)\)个点。每个点到下一层的每一个点都有连边。另外有\(k(k\le5\times10^4)\)条新边，从层数小的点到层数大的点。

问从第\(0\)层到第\(n+1\)层有几种方案。

思路：

将额外边上的点离散出来单独计算答案，不是额外边的点可以直接通过快速幂计算贡献。

时间复杂度\(\mathcal O(k\log k)\)。

源代码：

#include<map>

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

using int64=long long;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

using Point=std::pair<int64,int>;

constexpr int mod=1e9+7;

inline int power(int a,int64 k) {

	int ret=1;

	for(;k;k>>=1) {

		if(k&1) ret=(int64)ret*a%mod;

		a=(int64)a*a%mod;

	}

	return ret;

}

std::map<Point,std::vector<Point>> e;

std::map<Point,int> f;

std::map<int64,int> sum;

std::vector<int64> vx;

std::map<int64,std::vector<int>> vy;

int main() {

	const int64 n=getint();

	const int m=getint(),k=getint();

	const Point s=(Point){0,0},t=(Point){n+1,0};

	for(register int i=0;i<k;i++) {

		const int64 sx=getint();

		const int sy=getint();

		const int64 tx=getint();

		const int ty=getint();

		const Point a=(Point){sx,sy},b=(Point){tx,ty};

		e[b].emplace_back(a);

		if(a!=s) {

			vx.emplace_back(sx);

			vy[sx].emplace_back(sy);

		}

		if(b!=t) {

			vx.emplace_back(tx);

			vy[tx].emplace_back(ty);

		}

	}

	std::sort(vx.begin(),vx.end());

	vx.resize(std::unique(vx.begin(),vx.end())-vx.begin());

	sum[0]=f[s]=1;

	for(register unsigned i=0;i<vx.size();i++) {

		const int64 &x=vx[i],lastx=i?vx[i-1]:0;

		auto &sumx=sum[x];

		(sumx=(int64)sum[lastx]*power(m,x-lastx)%mod)%=mod;

		auto &vyx=vy[x];

		std::sort(vyx.begin(),vyx.end());

		vyx.resize(std::unique(vyx.begin(),vyx.end())-vyx.begin());

		for(register unsigned i=0;i<vyx.size();i++) {

			const int &y=vyx[i];

			const Point p=(Point){x,y};

			const auto &ep=e[p];

			auto &fp=f[p];

			for(register unsigned i=0;i<ep.size();i++) {

				const Point &q=ep[i];

				(fp+=f[q])%=mod;

			}

			(sumx+=fp)%=mod;

			(fp+=(int64)sum[lastx]*power(m,x-lastx-1)%mod)%=mod;

		}

	}

	(f[t]=(int64)sum[vx.empty()?0:*vx.rbegin()]*power(m,n-(vx.empty()?0:*vx.rbegin()))%mod)%=mod;

	for(register unsigned i=0;i<e[t].size();i++) {

		(f[t]+=f[e[t][i]])%=mod;

	}

	printf("%d\n",f[t]);

	return 0;

}