[CF 821E] Okabe and El Psy Kongroo

題目

洛谷

題意

給定一個二維座標系和一些線段，求從 $(0,0)$ 走到 $(k,0)$ 的方案總數。若當前座標爲 $(x,y)$，下一步可以拓展到 $(x+1,y+1)、(x+1,y)、(x+1,y-1)$。注意不能超出給出的線段——即爲上邊界。線段間沒有重疊和空隙，保證最後一條線段覆蓋 $k$。

首先，可以想到一個 $dp$，定義 $dp[i][j]$ 爲走到 $(i,j)$ 的方案數，那麼轉移就很顯然了：$dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]$，注意判斷邊界即可。

然而，$k<=1e18$，顯然 $T$ 到沒朋友。看到這麼大的數據範圍，首先想到——能否用矩陣加速呢？但是，右矩陣應該是在隨着上邊界而不斷改變的啊，怎麼辦呢？考慮到不同上邊界之間是遞推的關係，而上邊界的個數 $<=100$，做上邊界個數次矩陣快速冪即可。

時間複雜度 $O(n*log(k)*c[i]^3)$，大概在 $2e7$ 左右，跑過綽綽有餘。

Code：

struct Matrix
{
	LL n, m, c[MAXN][MAXN];
	Matrix(){memset(c, 0, sizeof c);}
	void Clear(){memset(c, 0, sizeof c);}
	friend Matrix operator *(Matrix A,Matrix B)
	{
		Matrix Res;
//		Res.Clear();
		Res.n = A.n, Res.m = B.m;
		for (Int k = 1; k <= B.n; ++ k)
			for (Int i = 1; i <= A.n; ++ i)
				for (Int j = 1; j <= A.m; ++ j)
					if ( B.c[k][j] )
						Res.c[i][j] += A.c[i][k] * B.c[k][j] % Mod,
						Res.c[i][j] %= Mod;
		return Res;
	}
	void Print()
	{
		for (Int i = 1; i <= n; ++ i, putchar('\n'))
			for (Int j = 1; j <= m; ++ j)
				printf("%lld ", c[i][j]);
	}
}A, B, C;
inline Matrix QuickPow(Matrix x,LL y)
{
	Matrix Temp;
//	Temp.Clear();
	Temp.n = Temp.m = x.m;
	for (Int i = 1; i <= x.m; ++ i)
		Temp.c[i][i] = 1;
	while ( y )
	{
		if (y & 1)
			Temp = Temp * x;
		x = x * x;
		y /= 2;
	}
	return Temp;
}
int main()
{
	LL n, k;
	read( n ); read( k );
	B.n = B.m = C.n = C.m = 16;
	for (Int i = 1; i <= 16; ++ i)
		C.c[i][i] = 1;
	for (Int i = 1; i <= n; ++ i)
	{
		LL a, b, c;
		read( a ); read( b ); read( c );
		c ++;
		b = Min(b, k);
		B.Clear();
		for (Int y = c; y >= 1; -- y)
		{
			if (y != c)
				B.c[y][y + 1] = 1;
			B.c[y][y] = 1;
			if (y != 1)
				B.c[y][y - 1] = 1;
		}
//		B.Print();
		C = C * QuickPow(B, b - a); 
	}
	A.n = 1, A.m = 16;
	A.c[1][1] = 1;
	A = A * C;
	printf("%lld", A.c[1][1]);
	return 0;
}