Luogu P3597 [POI2015]WYC___マトリックス乗算高速べき乗+乗数

テーマ:
n個の点mのエッジの帯域重み有向図が与えられ、各エッジのエッジ重みは1,2,3のいずれかである可能性がある.可能なすべてのパスをパス長で並べ替えます.k番目の小さなパスの長さを出力してください.パスは単純なパスではなく、同じ点を繰り返すことができることに注意してください.セルフループがなく、重いエッジがある可能性があります.1<=n<=40,1<=m<=1000,1<=k<=10^18
分析:
1つの点を3つに分割し、すべてのエッジ重みを1に分割し、行列乗算を行うことができます.計算を容易にするために、カウント点0を追加し、0が自己ループのような行列のx乗を接続したときのΣi=0 n(a i,0−1)sum_{i=0}^{n}(a_{i,0}−1)Σi=0 n(ai,0−1)は長さ<=x<=x<=xの場合のスキーム数であり,行列の2 i 2^i 2 i乗の場合のスキーム数を前処理して答えの統計O(n 3∗65+n 3 l o g 2 k)O(n^3*65+n^3 log 2 k)O(n 3∗65+n 3 log 2 k)O(n 3∗65+n 3 log 2 k)を最適化することができる.
コード:

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define rep(i, st, ed) for (int i = st; i <= ed; i++)
#define rwp(i, ed, st) for (int i = ed; i >= st; i--)

#define mt(x) memset(x, 0, sizeof(x))
#define mp(x, y) memcpy(x, y, sizeof(y))

#define N 1005
#define M 45

using namespace std;

typedef long long ll;

struct Matrix {
	ll a[M*3][M*3];
};
Matrix C[65], cc, cur, tmp;
int id[M][3], n, m, cnt, R;
ll K, ans, now;

Matrix operator * (Matrix &aa, Matrix &bb) {
    mt(cc.a);
	rep(i, 0, 3 * n) 
		rep(j, 0, 3 * n)
		    rep(k, 0, 3 * n) cc.a[i][j] += aa.a[i][k] * bb.a[k][j];
	return cc;	
}
bool check(Matrix &aa) {
    ll p = 0;
    rep(i, 1, n) {
        p += (aa.a[i][0] - 1);
        if (K <= p) return 1; 
    }
    return 0;
}

int main() {
	scanf("%d %d %lld", &n, &m, &K);
	rep(i, 1, n) C[0].a[i][0] = C[0].a[i][i + n] = C[0].a[i + n][i + 2 * n] = 1;
	int u, v, w;
	rep(i, 1, m) 
		scanf("%d %d %d", &u, &v, &w), ++C[0].a[u + (w - 1) * n][v];
	C[0].a[0][0] = 1;
	
	int R = 1;
    for (R; R <= 66; R++) {
        if (R > 65)  { printf("-1
"); return 0; }
        C[R] = C[R - 1] * C[R - 1];
        if (check(C[R])) break;
    }
    rep(i, 1, n) cur.a[i][i] = 1; 
	for(R--; ~R; --R) {
        tmp = cur * C[R];
        if (!check(tmp)) cur = tmp , ans += (1ll << R);
    }
	printf("%lld
", ans);
	return 0;
}