LGV 引理——2025.7.18 鮮花
LGV 引理
心靈感應
ねえもっとちょうだい?
nē motto choudai?
:-b ;-b boy, :-b ;-b boy, duh
:-b ;-b boy, :-b ;-b boy, duh
:-b ;-b boy, :-b ;-b boy, duh
:-b ;-b boy, :-b ;-b boy
べー! 気付(きず)いてよ
bē kizu ite yo
履修(りしゅう)してよ あたしのこと とんとん
rishū shite yo atashi no koto ton ton
もー、べー!嫌(きら)いだよ
mō bē kirai da yo
頭悪そうって顔するの のんのん
あたまわるそうってかおするののんのん
atama warusou tte kao suru no non non
さあ sā
勘繰(かんぐ)りダンス ブギウギ
kanguri dansu bugi ugi
迷子(まいご)でぼっち デビデビ
maigo de bocchi debi debi
感情(かんじょう)をください ハイハイ
kanjou wo kudasai hai hai
ぶー bū
配慮(はいりょ)んダンス ブギウギ
hairyo n dansu bugi ugi
解釈一致(かいしゃくいっち) ギミギミ
kaishaku icchi gimi gimi
返答(へんとう)をください ハイハイ
hentou wo kudasai hai hai
「期待しないで」とか今更で は?
「きたいしないで」とかいまさらで は?
"kitai shinaide" toka imasara de ha?
まじでSTOP 脈(みゃく)ナシハラスメント
maji de STOP myaku nashi harasumento
待ちに待った思春期頑張んべ
まちにまったししゅんき がんばんべ
machi ni matta shishunki ganbanbe
あいうぉんちゅーコールが聞(き)こえなーい
ai uonchu kōru ga kikoenā i
伝播する義務ラブ マッチング
でんぱするぎむラブ マッチング
denpa suru gimu rabu macchingu
要承認(ようしょうにん)ハートのリハしたい
youshounin haato no riha shitai
ライブでは下手(へた)くそ やんなっちゃう
raibu de wa hetakuso yanna cchau
はぁ「戀愛ガールは葉えたい」
はぁ「れんあいガールはかなえたい」
hā "ren'ai gāru wa kanae tai"
衝撃のアニメ化待っています
しょうげきのあにめかまっています
shougeki no animeka matte imasu
アンハッピーエンドじゃつまんない
an happī endo ja tsuman nai
“feat. きみ”を ねえもっとちょうだい?
“feat. kimi ” wo nē motto choudai ?
:-b ;-b boy, :-b ;-b boy, duh
:-b ;-b boy, :-b ;-b boy, duh
:-b ;-b boy, :-b ;-b boy, duh
:-b ;-b boy, :-b ;-b boy
ねえ 気付(きず)いても
nē kizuite mo
無視()するとこ そういうとこ
mushi suru toko sou iu toko
ねえ 嫌(きら)いだと
nē kirai da to
思(おも)えるほど 強(つよ)くないの
omoeru hodo tsuyokunai no
さあ テンパりトーク ドギマギ
sā tenpari tooku dogi'magi
ハードなチャンス デビデビ
haado na chansu debi'debi
原稿(げんこう)をください ハイハイ
genkou wo kudasai hai'hai
さあ ギャンブルトーク ドギマギ
sā gyanburu tooku dogi'magi
戀(こい)$ベット デビデビ
koi $ betto debi'debi
全勝(ぜんしょう)をください ハイハイ
zenshou wo kudasai hai'hai
わああああああ は??
wā ā ā ā ha ? ?
まじでSTOP 逆張り harassment
まじでSTOP ぎゃくはりハラスメント
majide STOP gyaku hari harasumento
勝ちに行って負けるの何回目 嫌になんぜ
かちにいってまけるのなんかいめいやになんぜ
kachi ni itte makeru no nan kaime iya ni nanze
あいうぉんちゅーコール伝(つた)わんない
ai uonchu kōru tsuta wannai
飽和する telepathy zapping
ほうわするテレパシ ザッピング
houwa suru terepashi zappingu
妄想継承 して revenger
もうそうけいしょうしてリベンジャー
mousou keishou shite ribenjaa
先帝の無念晴らしてやる
せんていのむねんはらしてやる
sentei no munen harashite yaru
はぁ「転生(てんせい)したらあたしだった」
hā " tensei shi'tara atashi datta "
大好きの壁打ちやっています
だいすきのかべちやっています
daisuki no kabe uchi yatte imasu
アンハッピーエンドじゃつまんない
an happī endo ja tsuman nai
“feat. きみ”を ねえもっとちょうだい?
“feat. kimi ” wo nē motto choudai ?
:-Duh yeah, :-D ;-Duh yeah
:-Duh yeah, :-D ;-Duh yeah
:-Duh yeah, :-D ;-Duh yeah
:-Duh yeah, :-D ;-Duh yeah
あいうぉんちゅーコールが聞(き)こえなーい
ai uonchu kōru ga kikoenā i
アンハッピーエンドじゃつまんない
an happī endo ja tsuman nai
“feat. きみ”を ねえもっとちょうだい?
“feat. kimi ” wo nē motto choudai ?

很簡單的。
就是每條邊有邊權 \(w_i\),設 \(e(u, v)\) 表示 \(u \rightsquigarrow v\) 的每一條路徑的邊權和,\(A_i\) 是起點集合,\(B_i\) 是終點集合,矩陣:
\[ M =
\begin{bmatrix}
e(A_1, B_1) & \cdots & e(A_1, B_n)\\
\vdots & \ddots & \vdots \\
e(A_n, B_1) & \cdots & e(A_n, B_n)
\end{bmatrix}\]
有:
\[\rm det(M)= \sum_{S: A\to B} (-1)^{\sigma(S)}\prod_{s \in S} w(s)
\]
其中 \(w(s)\) 表示 \(s\) 這條路徑的邊權積,\(S: A\to B\) 表示 \(S\) 是有 \(A\) 和 \(B\) 中的點兩兩配對形成的不交路徑集,\(\sigma(S)\) 表示這種配對的逆序對個數。
先來個板子:P6657 【模板】LGV 引理】
考慮到 \(a\) 和 \(b\) 匹配只有 \(a_i\) 匹配 \(b_i\) 是有值的,所以直接寫 LGV 即可。
首先發現其交點個數的奇偶和逆序對奇偶是是一樣的,直接上 LGV 即可。
好題。
考慮轉化成一些值域分割線從左上角走到右下角的方案,先平移一下變成不交。
限制相當于是恰有 \(k\) 條線從點的上方經過,設一些邊的邊權是 \(x\) 后提取 \(x^k\) 項系數即可。
不太能直接帶著多項式求行列式,這里直接拉插即可。
Code
/*
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && time ./%< && size %<
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && time ./%< && size %<
echo && cat out.out && echo
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
#endif
const int N = 403, K = 103, MOD = 998244353;
int n, m, _k, _r, _c, _v, cd[N][N][2], c[N][N];
int INV(int a, int b){ return a == 1 ? 1 : b - 1ll * INV(b % a, a) * b / a; }
int Inv(int a, int b = MOD){ return INV(a < 0 ? a + b : a, b); }
llt dp[N][N][2];
int Det(int c[N][N], int n){
int v = 1;
for(int i = 1; i <= n; ++i){
int t = i; for(; t <= n; ++t) if(c[t][i]) break;
if(t > n) continue;
if(t != i) swap(c[i], c[t]), v = -v;
for(int j = i + 1; j <= n; ++j){
int x = 1ll * Inv(c[i][i]) * c[j][i] % MOD;
for(int k = i; k <= n; ++k) c[j][k] = (c[j][k] - 1ll * c[i][k] * x) % MOD;
}
}
int r = 1;
for(int i = 1; i <= n; ++i) r = 1ll * r * c[i][i] % MOD;
return r * v;
}
class LGG{
private:
int dp[K]; vector<int> ob;
int Dp(int k){
memset(dp, 0, sizeof dp), dp[0] = 1;
for(auto b : ob){
for(int i = k; i; --i) dp[i] = (dp[i - 1] + 1ll * dp[i] * b) % MOD;
dp[0] = 1ll * dp[0] * b % MOD;
}
return dp[k];
}
public:
int y[K];
int operator()(int n, int k){
int r = 0;
for(int i = 1; i <= n; ++i){
ob.clear(); int s = 1;
for(int j = 1; j <= n; ++j) if(j != i) ob.emplace_back(-j), s = 1ll * s * (i - j) % MOD;
r = (r + 1ll * y[i] * Inv(s) % MOD * Dp(k)) % MOD;
}
return r;
}
} Lgg;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> _k >> _r >> _c >> _v, --_v, _r = _r + _v - 1, _c = _c + _v - 1, --_k;
for(int u = 1; u <= _k; ++u){
memset(dp, 0, sizeof dp), dp[u - 1][m + u][0] = 1;
for(int i = u; i <= n + _k; ++i) for(int j = m + u; j; --j) if(i != _r + 1 || j != _c + 1){
llt *d = dp[i][j];
d[0] += dp[i][j + 1][0] + dp[i - 1][j][0], d[1] += dp[i][j + 1][1] + dp[i - 1][j][1];
if(i <= _r && i - j == _r - _c) d[1] += d[0], d[0] = 0;
d[0] %= MOD, d[1] %= MOD;
}
for(int v = 1; v <= _k; ++v) cd[u][v][0] = dp[n + v][v][0], cd[u][v][1] = dp[n + v][v][1];
}
for(int x = 1; x <= _k + 1; Lgg.y[x++] = Det(c, _k)) for(int i = 1; i <= _k; ++i) for(int j = 1; j <= _k; ++j)
c[i][j] = (cd[i][j][0] + 1ll * cd[i][j][1] * x) % MOD;
cout << (Lgg(_k + 1, _v) + MOD) % MOD << endl;
}
P





本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18991145
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號