网站建设套餐报价,wordpress pdf 下载,营销策划与运营的书,ps做网站首页设计教程题目链接
题目大意#xff1a;给你n个范围[ l i , r i l_i,r_i li,ri]#xff0c;每个位置可以在这个范围中选择一个数#xff0c;然后形成排列1到n的排列p。问p的所有情况的个数的奇偶性。
一个很妙的行列式转化#xff0c;纯纯的线性代数。 首先#xff0c;我们把…题目链接
题目大意给你n个范围[ l i , r i l_i,r_i li,ri]每个位置可以在这个范围中选择一个数然后形成排列1到n的排列p。问p的所有情况的个数的奇偶性。
一个很妙的行列式转化纯纯的线性代数。 首先我们把p的总数表示出来。设矩阵 a i , j a_{i,j} ai,j表示的是第 i 个 i个 i个位置的是否可以表示 j j j。则p的所有可能为 ∑ p Π i 1 n a i , P i \sum\limits_{p}\mathop{\Pi}\limits_{i1}^{n}a_{i,Pi} p∑i1Πnai,Pi 其中p表示所有排列方式的总和。发现这是近似于矩阵a的行列式的值不过去掉了其正负号。在取模2的影响下综合的加减没有影响也就是说只要我们求矩阵 a a a的行列式的值 m o d 2 mod\ 2 mod 2就可以解出最终解。 根据矩阵的性质矩阵的行列式 m o d 2 mod\ 2 mod 2为 0 0 0等价于该矩阵 m o d 2 mod\ 2 mod 2下不可逆也等价于该矩阵 m o d 2 mod\ 2 mod 2下的每一行的向量存在线性相关也就是存在其中一个向量可以被其它向量表示。
至此我们终于该题从看不懂的样子转化成了看起来像人话的子问题了。让我们解决这个子问题。每一个位置的向量[ l i , r i l_i,r_i li,ri]我们可以通过 r i − ( l i − 1 ) r_i-(l_{i}-1) ri−(li−1)表示然后通过并查集判断出该向量能否通过其它向量表示。
int n,m;int pre[1000005];int find (int x){if(pre[x]x)return x;else return pre[x]find(pre[x]);
}void icealsoheat(){cinn;for(int i0;in;i)pre[i]i;int ans1;for(int i1;in;i){int l,r;cinlr;lfind(l-1);rfind(r);if(lr){ans0;// break;}else{pre[l]r;}}coutans\n;}
