公司网站开发创业,苏州吴江建设局招投标网站,大连网站设计公司,重庆市区旅游必去景点正题
题目链接:https://www.luogu.com.cn/problem/P7736 题目大意
有kkk层的图#xff0c;第iii层有nin_ini个点#xff0c;每层的点从上到下排列#xff0c;层从左到右排列。再给出连接相邻层的一些有向边#xff08;从iii层连向i1i1i1层#xff09;。 对于n1n_1n1…正题
题目链接:https://www.luogu.com.cn/problem/P7736 题目大意
有kkk层的图第iii层有nin_ini个点每层的点从上到下排列层从左到右排列。再给出连接相邻层的一些有向边从iii层连向i1i1i1层。 对于n1n_1n1层每个点作为起点同时出发走到不同的nkn_knk层的点的所有路径方案中交点数量为偶数的减去为奇数的方案有多少个。
1≤k≤100,2≤n1≤100,n1nk,n1≤ni≤2×n1,1≤T≤51\leq k\leq 100,2\leq n_1\leq 100,n_1n_k,n_1\leq n_i\leq 2\times n_1,1\leq T\leq 51≤k≤100,2≤n1≤100,n1nk,n1≤ni≤2×n1,1≤T≤5 解题思路
分析一下若第111层起点1,21,21,2分别对应终点1,21,21,2记fi,1/2f_{i,1/2}fi,1/2表示1/21/21/2在第iii层的位置。中间某个位置他们路径有了交点那么一定满足他们存在一层使得fi,1fi,2f_{i,1}f_{i,2}fi,1fi,2但是因为f1,1f1,2f_{1,1}f_{1,2}f1,1f1,2且fn,1fn,2f_{n,1}f_{n,2}fn,1fn,2也就是说明前后都各有一个交点。 拓展一下也就是说中间的路径走法不影响交点的奇偶性只有起点和终点会影响奇偶性。再进一步说路径交点的奇偶性就是起点对应终点的排列pip_ipi的逆序对数量的奇偶性。
设排列ppp表示起点iii会走到终点pip_ipiσ(p)\sigma(p)σ(p)表示排列ppp的逆序对数量w(p)w(p)w(p)表示排列ppp的路径方案 那么答案就是 ∑(−1)σ(p)w(p)\sum (-1)^{\sigma(p)}w(p)∑(−1)σ(p)w(p) 发现和LGVLGVLGV引理的式子一模一样直接上就好了
时间复杂度O(T(k2nn3))O(T(k^2nn^3))O(T(k2nn3)) code
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includevector
#define ll long long
using namespace std;
const ll N210,P998244353;
ll T,k,n[N],m[N],f[N][N],a[N][N];
vectorint G[N][N];
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll det(ll n){ll ans1,f1;for(ll i1;in;i){for(ll ji;jn;j)if(a[j][i]){if(j!i)swap(a[j],a[i]),f!f;break;}ll invpower(a[i][i],P-2);ansans*a[i][i]%P;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 f?ans:((P-ans)%P);
}
signed main()
{Tread();while(T--){kread();for(ll i1;ik;i)n[i]read();for(ll i1;ik;i)m[i]read();for(ll i1;ik;i){for(ll j1;jm[i];j){ll xread(),yread();G[i][x].push_back(y);}}for(ll i1;in[k];i){f[k][i]1;f[k][i-1]0;for(ll jk-1;j1;j--)for(ll x1;xn[j];x){f[j][x]0;for(ll p0;pG[j][x].size();p)(f[j][x]f[j1][G[j][x][p]])%P;}for(ll j1;jn[1];j)a[j][i]f[1][j];}f[k][n[k]]0;printf(%lld\n,det(n[1]));for(ll i1;ik;i)for(ll j1;jn[i];j)G[i][j].clear();}return 0;
}
