做网站的工作,聊城开发区建设局网站,免费的个人网站注册,wordpress栏目标题正题
题目链接:https://www.luogu.com.cn/problem/P6657 题目大意
给出nnn\times nnn的棋盘#xff0c;mmm个起点第iii个为(1,ai)(1,a_i)(1,ai)#xff0c;对应mmm个终点第iii个为(n,bi)(n,b_i)(n,bi)。
求有多少条选出mmm条四联通路径的方案使得没有路径有交点。 2≤…正题
题目链接:https://www.luogu.com.cn/problem/P6657 题目大意
给出n×nn\times nn×n的棋盘mmm个起点第iii个为(1,ai)(1,a_i)(1,ai)对应mmm个终点第iii个为(n,bi)(n,b_i)(n,bi)。
求有多少条选出mmm条四联通路径的方案使得没有路径有交点。
2≤n≤106,1≤m≤100,1≤T≤52\leq n\leq 10^6,1\leq m\leq 100,1\leq T\leq 52≤n≤106,1≤m≤100,1≤T≤5 解题思路
既然是引理我直接上证明了设矩阵AAA中Ax,yA_{x,y}Ax,y为第xxx个起点走到第yyy个起点的所有路径权值乘积和这题里面为111。
然后答案就是所有方案的路径权值乘积这个矩阵的行列式。
具体证明是容斥但是我不会。
时间复杂度O(nTm3)O(nTm^3)O(nTm3) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e610,P998244353;
ll T,n,m,fac[N],inv[N],b[110],c[110],a[110][110];
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
ll Path(ll x,ll y){if(b[x]c[y])return 0;return C(c[y]-b[x]n-1,n-1);
}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll dec(ll n){ll ans1,f1;for(ll i1;in;i){for(ll ji;jn;j){if(a[j][i]){if(j!i)swap(a[i],a[j]),f-f;break;}}ansans*a[i][i]%P;ll invpower(a[i][i],P-2);for(ll ji;jn;j)a[i][j]a[i][j]*inv%P;for(ll ji1;jn;j){ll rateP-a[j][i];for(ll ki;kn;k)(a[j][k]rate*a[i][k]%P)%P;}}return ans;
}
signed main()
{scanf(%lld,T);inv[1]1;for(ll i2;iN;i)inv[i]P-inv[P%i]*(P/i)%P;fac[0]inv[0]1;for(ll i1;iN;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P;while(T--){scanf(%lld%lld,n,m);for(ll i1;im;i)scanf(%lld%lld,b[i],c[i]);for(ll i1;im;i)for(ll j1;jm;j)a[i][j]Path(i,j);printf(%lld\n,dec(m));}return 0;
}
