[CC-CHEFGRPH]Time to Study Graphs with Chef

[CC-CHEFGRPH]Time to Study Graphs with Chef

题目大意：

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

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

思路：

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

时间复杂度(mathcal O(klog 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
",f[t]);
	return 0;
}