【学习笔记】 LGV引理

LGV引理

在一个有向无环图G中，出发点 $A=\{a_1,a_2,...a_n\}$ ，目标点 $B=\{b_1,b_2,..b_n\}$ 。有向边 $e$ 的权值为 $w_e$ ， $e (u, v)$ 为路径边权乘积之和，即 $e(u,v)=\sum_{P:a->b}\prod_{e\in P}w_e$

则 $\begin{vmatrix} e(a_1,b_1)& e(a_1,b_2) & ... & e(a_1,b_n)\\ e(a_2,b_1)& e(a_2,b_1) & ... & e(a_2,b_n)\\ ...& ... & & ...\\ e(a_n,b_1)& e(a_n,b_2) & ... & e(a_n,b_n) \end{vmatrix}=\sum_{S:A->B}(-1)^{N(\sigma)}\prod_{i=1}^n\prod_{e\in S_i}w_e$

其中 $\sigma$ 是一个n元置换， $N(\sigma)$ 表示逆序对个数, $S_i:a_i->b_i$ 是一组A到B的不相交路径。

如果我们将行列式展开，可以得到下式：

$\sum_{P}(-1)^{\sigma(P)}\prod_{i=1}^{n}e(a_i,P(a_i))=\sum_{S:A->B}(-1)^{N(\sigma)}\prod_{i=1}^n\prod_{e\in S_i}w_e$

其中 $\sigma(P)$ 就表示P的逆序对个数

此处的不相交是指处处不存在相同的点在两条路径中同时存在，起终点也不行，所以A里的元素互不相同。如果初始条件并非如此，可能要转化一下

在算法竞赛中，该引理在普通的DAG下没有过多的用处，因为其右式还是过于复杂。但是如果图满足所有边权为1（这样 $e(u,v)\equiv1$ ,就可以表示路径数量了），并且只存在唯一的一个$\sigma $满足所有$ a_i->b_i$不相交的话(满足是平面图)，此时右式只有一个因子，含义就是整张图的不相交路径组数，就可以用左式的行列式表示了

Monotonic Matrix

大意：

$A_1(1,0),A_2(0,1),B_1(n,m+1),B_2(n+1,m)$ ,求 $A_1->B_1,A_2->B_2$ 的不相交路径数。其中每一步只能向上/向右

套板子即可

#include <bits/stdc++.h>
#define pii pair<int,int>
#define il inline
#define ll long long
using namespace std;
const int N=2010;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m;
ll c[N][N];
void init(ll n)
{for(int i=0;i<=n;++i){for(int j=0;j<=i;++j){if(j==0) c[i][j]=1;else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}
}
ll f(ll x1,ll y1,ll x2,ll y2)
{//(x1,y1)->(x2,y2)ll len1=x2-x1;ll len2=y2-y1;return c[len1+len2][len2];
}
void solve()
{// cin>>n>>m;ll a=f(0,1,n,m+1)*f(1,0,n+1,m)%mod;ll b=f(0,1,n+1,m)*f(1,0,n,m+1)%mod;cout<<((a-b)%mod+mod)%mod<<endl;
}
int main()
{
//     freopen("1.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init(2005);while(cin>>n>>m)// ll t;cin>>t;while(t--)solve();return 0;
}

abc216 H Random Robots

大意：
x轴上有k个点 $a_i$ ，n秒钟，每一秒对于每一个点来说，有一半概率保持不动，有一半的概率前进1个单位，求k个点两两碰撞的概率

思路：

n秒种两两不碰撞，这提示我们使用LGV引理。可以将题目再转化一下： $(x, y)$ 在每一秒种有一半的概率移动到 $(x, y + 1)$ ,有一半的概率移动到 $(x + 1, y + 1)$ ,这样就相当于求k条不相交路径的方案数了。

虽然但是，我们的终点是不确定的，所以直接枚举每一个起点对应的终点然后再算行列式的话，是不行的。注意到k只有10，这提示我们使用状压dp来处理。

不妨采用上面对行列式的展开： $\sum_{P}(-1)^{\sigma(P)}\prod_{i=1}^{n}e(a_i,P(a_i))=\sum_{S:A->B}(-1)^{N(\sigma)}\prod_{i=1}^n\prod_{e\in S_i}w_e$

对于左式，我们实际上是要算逆序对个数为偶数的所有置换对应的方案数减去逆序对个数为奇数的方案数

考虑 $dp_{s,j}$ 表示考虑的点集为s $\in [1,2^k-1]$ ,每一个点的最大横坐标不超过j的所有带标号方案数之和。这里带标号是指带上 $(-1)^{\sigma(P)}$ 作为系数

转移方程如下： $dp_{s,j}=dp_{s,j-1}+\sum_{i\in s}(-1)^{Greater(i)}dp_{s-\{i\},j-1}\binom{n}{j-a_i}$

这里我们枚举i并将其放在置换P的最后一个位置j， $G re a t er (i)$ 表示在 $s-\{i\}$ 中有多少个数比i大，又因为i放在最后一个位置，所以如果我们倒序遍历S中的元素i的话，对于 $(-1)^{\sigma(P)}$ 这个系数就能做到 $O (1)$ 更新了。那么如果 $G re a t er (i)$ 是一个偶数，就意味着加入i不会改变当前序列逆序对数的奇偶性，所以直接加就好了，否则要取负。 $\binom{n}{j-a_i}$ 表示从 $a_i$ 到 $j$ 的方案数在，这个显然

那么这样之后就可以把合法的方案数求出来了，再除以总方案数 $2^{kn}$ 即可

#include <bits/stdc++.h>
#define pii pair<int,int>
#define il inline
#define ll long long
using namespace std;
const int N=2020;
const ll inf=1e18;
const ll mod=998244353ll;
ll n,m;
ll mas[N];
ll ksm(ll x,ll y)
{ll ans=1;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;
}
ll inv(ll x)
{return ksm(x,mod-2);
}
ll p[N],pp[N];
ll dp[2030][2010];
void init(ll n)
{p[0]=1;for(ll i=1;i<=n;++i) p[i]=p[i-1]*i%mod;pp[n]=inv(p[n]);for(ll i=n-1;i>=0;--i) pp[i]=pp[i+1]*(i+1)%mod;
}
ll C(ll n,ll m)
{if(m<0) return 0;if(n<m) return 0;return p[n]*pp[m]%mod*pp[n-m]%mod;
}
void solve()
{init(2005);cin>>n>>m;//n个人，m步ll ma=0;for(int i=1;i<=n;++i) cin>>mas[i],mas[i]++,ma=max(ma,mas[i]+m);ll pre,idx;for(int i=0;i<=ma;++i) dp[0][i]=1;for(int s=1;s<(1<<n);++s){for(int j=1;j<=ma;++j){dp[s][j]=dp[s][j-1];ll cn=0;for(int i=n;i;--i){if(((s>>(i-1))&1)==0) continue;pre=s^(1<<(i-1));idx=((cn%2)?mod-1:1ll);dp[s][j]=(dp[s][j]+dp[pre][j-1]*idx%mod*C(m,j-mas[i])%mod)%mod;cn++;}}}// cout<<(1<<n)-1<<" "<<ma<<" "<<dp[(1<<n)-1][ma]<<endl;cout<<dp[(1<<n)-1][ma]*inv(ksm(2,n*m))%mod<<endl;}
int main()
{// freopen("1.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}

cells

大意：

n个点,第i个点 $0,a_i)(a_i>0)$ 要移动到 $(i, 0)$ ,每一个点每次可以向右/向下移动，求路径不相交方案数， $n\leq 1e5$

思路：
题意就是一个裸的LGV引理，但是如何求行列式是一个问题。这里数据范围都比较大，所以用状压dp什么的就不要想了

$\begin{vmatrix} e(a_1,b_1) & e(a_1,b_2) & ... &e(a_1,b_n) \\ e(a_2,b_1) & e(a_2,b_2) & ... &e(a_2,b_n) \\ ... & ... & & ... \\ e(a_n,b_1) & e(a_n,b_2) & ... & e(a_n,b_n) \end{vmatrix}=\begin{vmatrix} \binom{a_1+1}{a_1} & \binom{a_1+2}{a_1} & ... &\binom{a_1+n}{a_1} \\ \binom{a_2+1}{a_2} & \binom{a_2+2}{a_2} & ... &\binom{a_2+n}{a_2} \\ ... & ... & & ... \\ \binom{a_n+1}{a_n} & \binom{a_n+2}{a_n} & ... & \binom{a_n+n}{a_n} \end{vmatrix}=\prod_{i=1}^{n}\frac{1}{i!}\begin{vmatrix} \frac{(a_1+1)!}{a_1!} & \frac{(a_1+2)!}{a_1!} & ... &\frac{(a_1+n)!}{a_1!} \\ \frac{(a_2+1)!}{a_2!} & \frac{(a_2+2)!}{a_2!} & ... &\frac{(a_2+n)!}{a_2!} \\ ... & ... & & ... \\ \frac{(a_n+1)!}{a_n!} & \frac{(a_n+2)!}{a_n!} & ... & \frac{(a_n+n)!}{a_n!} \end{vmatrix}$

$=\prod_{i=1}^{n}\frac{1}{i!}\begin{vmatrix} (a_1+1) & (a_1+1)(a_1+2) & ... &(a_1+1)(a_1+2)...(a_1+n) \\ (a_2+1) & (a_2+1)(a_2+2) & ... &(a_2+1)(a_2+2)...(a_2+n) \\ ... & ... & & ... \\ (a_n+1) & (a_n+1)(a_n+2) & ... &(a_n+1)(a_n+2)...(a_n+n) \\ \end{vmatrix}$

不难发现经过列转换可以变成下式

$=\prod_{i=1}^{n}\frac{1}{i!}\begin{vmatrix} (a_1+1) & (a_1+1)^2 & ... &(a_1+1)^n \\ (a_2+1) & (a_2+1)^2 & ... &(a_2+1)^n \\ ... & ... & & ... \\ (a_n+1) & (a_n+1)^2 & ... &(a_n+1)^n \\ \end{vmatrix}$

提出 $a_i+1)!$ 之后里面是一个范德蒙德行列式

$=\prod_{i=1}^{n}\frac{1}{i!}(a_i+1)!\begin{vmatrix} 1 & (a_1+1)^1 & ... &(a_1+1)^{n-1} \\ 1 & (a_2+1)^1 & ... &(a_2+1)^{n-1} \\ ... & ... & & ... \\ 1 & (a_n+1)^1 & ... &(a_n+1)^{n-1} \\ \end{vmatrix}=(\prod_{i=1}^{n}\frac{1}{i!}(a_i+1)!)(\prod_{1\leq i<j\leq n}a_j-a_i)$

前面一个式子可以快速处理，关键就是后面的式子要怎么快速求

不难发现我们的目标应该是求出所有 $a_j-a_i$ 的值的出现次数，然后快速幂即可

涉及到出现次数，可以考虑使用卷积。我们将 $a_j-a_i$ 看成 $a_j+(-a_i)$ ,将其看成形式变量的指数次数的话，一个式子的所有指数次数是 $a_i$ ,令一个式子的指数次数是 $m-a_i$ ,卷积之后其对应的系数就是出现次数。这里为了防止计算负数，加入偏移量m,保证 $\forall i,m-i\geq 0$ 即可.

但是我们只要 $a_j-a_i$ ,直接卷积的话，指数范围是 $[0, 2 m]$ 是偏多的：加入偏移量之后， $a_j-a_i$ 变成 $a_j+m-a_i>m$ ,所以我们只要在 $[m + 1, 2 m]$ 范围内查看就好了

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;#define N maxn
#define db double
#define il inline
#define fir first
#define sec second
#define eps (1e-8)
#define pb push_back
#define ll long long
#define mkp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define lowbit(a) (a & (-a))
#define SZ(a) ((int)a.size())
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define split cout << "=========\n";
#define GG { cout << "NO\n"; return; }
#define pll pair<long long, long long>
#define equals(a, b) (fabs((a) - (b)) < eps)constexpr int ON = 0;
constexpr int CW = -1;
constexpr int CCW = 1;
constexpr int BACK = 2;
constexpr int FRONT = -2;
const db pi = acos(-1.000);
constexpr int maxn = 2e6 + 50;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF =  0x3f3f3f3f3f3f3f3f;
constexpr int mod = 998244353; /* 1e9 + 7 */
constexpr int dir[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};mt19937_64 rnd(random_device {}());
uniform_int_distribution<ull> dist(0, ULLONG_MAX);//use dist(rnd)bool BEGIN;
ll qpow(ll x,ll y)
{ll ans=1;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;
}
ll inv(ll x)
{return qpow(x,mod-2);
}namespace Poly
{#define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)#define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)#define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)//上面其实没用到#define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了typedef vector<int> poly;const int G = 3;//根据具体的模数而定，原根可不一定不一样！！！//一般模数的原根为 2 3 5 7 10 6const int inv_G = qpow(G, mod - 2),tt = 23;int deer[2][tt][(1 << tt)];vector<int>RR(1 << (tt + 1), 0),inv(1 << tt, 0);void init(const int t) {//预处理出来NTT里需要的w和wn，砍掉了一个log的时间assert(t < tt);//一定要注意！！for(int p = 1; p <= t; ++ p) {int buf1 = qpow(G, (mod - 1) / (1 << p));int buf0 = qpow(inv_G, (mod - 1) / (1 << p));deer[0][p][0] = deer[1][p][0] = 1;for(int i = 1; i < (1 << p); ++ i) {deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;}}inv[1] = 1;for(int i = 2; i <= (1 << t); ++ i)inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;}int NTT_init(int n) {//快速数论变换预处理int limit = 1, L = 0;while(limit <= n) limit <<= 1, L ++ ;assert(L < tt);assert(limit < 1 << (tt + 1));for(int i = 0; i < limit; ++ i)RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));return limit;}void NTT(poly &A, bool type, int limit) {//快速数论变换A.resize(limit);for(int i = 0; i < limit; ++ i)if(i < RR[i])swap(A[i], A[RR[i]]);for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {int len = mid >> 1;for(int pos = 0; pos < limit; pos += mid) {
//                auto wn = deer[type][j].begin();for(int i = pos, p = 0; i < pos + len; ++ i, ++ p) {int tmp = 1ll * deer[type][j][p] * A[i + len] % mod;A[i + len] = ck(A[i] - tmp + mod);A[i] = ck(A[i] + tmp);}}}if(type == 0) {for(int i = 0; i < limit; ++ i)A[i] = 1ll * A[i] * inv[limit] % mod;}}poly poly_mul(poly A, poly B) {//多项式乘法int deg = A.size() + B.size() - 1;int limit = NTT_init(deg);poly C(limit);NTT(A, 1, limit);NTT(B, 1, limit);for(int i = 0; i < limit; ++ i)C[i] = 1ll * A[i] * B[i] % mod;NTT(C, 0, limit);C.resize(deg);return C;}poly poly_inv(poly &f, int deg) {//多项式求逆 deg<f.szie()if(deg == 1)return poly(1, qpow(f[0], mod - 2));poly A(f.begin(), f.begin() + deg);poly B = poly_inv(f, (deg + 1) >> 1);int limit = NTT_init(deg << 1);NTT(A, 1, limit), NTT(B, 1, limit);for(int i = 0; i < limit; ++ i)A[i] = B[i] * (2 - 1ll * A[i] * B[i] % mod + mod) % mod;NTT(A, 0, limit);A.resize(deg);return A;}poly poly_dev(poly f) {//多项式求导int n = f.size();for(int i = 1; i < n; ++ i) f[i - 1] = 1ll * f[i] * i % mod;if(n > 1)f.resize(n - 1);else f[0] = 0;return f.resize(n - 1), f;//求导整体左移，第0项不要}poly poly_idev(poly f) {//多项式求积分int n = f.size();for(int i = n - 1; i ; -- i) f[i] = 1ll * f[i - 1] * inv[i] % mod;return f[0] = 0, f;//积分整体右移，第0项默认为0}poly poly_ln(poly f, int deg) {//多项式求对数，第一项为1poly A = poly_idev(poly_mul(poly_dev(f), poly_inv(f, deg)));return A.resize(deg), A;}poly poly_exp(poly &f, int deg) {//多项式求指数，第一项为0if(deg == 1)return poly(1, 1);poly B = poly_exp(f, (deg + 1) >> 1);B.resize(deg);poly lnB = poly_ln(B, deg);for(int i = 0; i < deg; ++ i)lnB[i] = ck(f[i] - lnB[i] + mod);int limit = NTT_init(deg << 1);//n -> n^2NTT(B, 1, limit), NTT(lnB, 1, limit);for(int i = 0; i < limit; ++ i)B[i] = 1ll * B[i] * (1 + lnB[i]) % mod;NTT(B, 0, limit);B.resize(deg);return B;}poly poly_pow(poly f, int k) {//多项式快速幂,第一项得是1f = poly_ln(f, f.size());for(auto &x : f) x = 1ll * x * k % mod;return poly_exp(f, f.size());}poly poly_ksm(poly f, int k,int m) {//多项式快速幂,适用于初始只有几项，同时所有项都需要的情况,会比上面那个快一点poly res(1, 1);while(k){if(k & 1){res = poly_mul(res, f);res.resize(m,0);}f = poly_mul(f, f);f.resize(m,0);k >>= 1;}return res;}
}using Poly::poly;
using Poly::poly_pow;
using Poly::poly_ksm;
using Poly::poly_mul;
using Poly::poly_inv;
ll p[N],pp[N],C[N];
void init(ll n)
{p[0]=1;for(ll i=1;i<=n;++i) p[i]=p[i-1]*i%mod;pp[n]=inv(p[n]);for(ll i=n-1;i>=0;--i) pp[i]=pp[i+1]*(i+1)%mod;
}ll n,m,k;
ll mas[N];
ll ma=0;
void solve()
{Poly::init(22);cin>>n;for(int i=1;i<=n;++i) cin>>mas[i],ma=max(ma,mas[i]);poly f,g;f.resize(ma+1);g.resize(ma+1);for(int i=1;i<=n;++i){f[mas[i]]=1;g[ma-mas[i]]=1;}ll ans=1;for(int i=1;i<=n;++i){ans=ans*pp[i]%mod*(mas[i]+1)%mod;}f=poly_mul(f,g);for(int i=ma+1;i<=ma*2;++i){if(f[i]==0) continue;ll det=i-ma;ans=ans*qpow(det,f[i])%mod;}cout<<ans<<endl;
}bool END;
signed main() {// cout << fixed << setprecision(10);ios::sync_with_stdio(false); cin.tie(nullptr);init(2000000);// int T; cin >> T; while (T--)solve();// cout << ((&END - & BEGIN) >> 21) << '\n';return 0;
}