codeforces736D. Permutations(线性代数)
2018-08-05 07:41:55来源:博客园 阅读 ()
题意
$m \leqslant 500000$,题目打错了
Sol
神仙题Orz
构造矩阵$B$,使得$B[b[i]][a[i]] = 1$
那么他的行列式的奇偶性也就对应了生成排列数列数量的奇偶性(定义)
删除一个位置相当于去掉对答案的贡献,也就是代数余子式的值
代数余子式可以由伴随矩阵求出$A^{*} = |A| A^{-1}$
这里只需要奇偶性,因此不需要求出实际行列式的值。
矩阵可以用bitset加速,可以过掉这个题
#include<cstdio> #include<bitset> #include<iostream> using namespace std; const int MAXN = 2001; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; bitset<MAXN * 2 + 10> b[MAXN]; int x[500001], y[500001]; int main() { N = read(); M = read(); for(int i = 1; i <= N; i++) b[i][i + N] = 1; for(int i = 1; i <= M; i++) { x[i] = read(), y[i] = read(); b[x[i]][y[i]] = 1; } for(int i = 1, j; i <= N; i++) { for(j = i; j <= N; j++) if(b[j][i]) {swap(b[i], b[j]); break;} for(int k = 1; k <= N; k++) if(b[k][i] && (k != i)) b[k] ^= b[i]; } for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= 2 * N; j++) cout << b[i][j] << " "; return 0; } /* 3 7 1 1 1 3 2 2 2 3 3 1 3 2 3 3 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 非常详细的 Linux C/C++ 学习路线总结!已拿腾讯offer 2020-03-29
- 数据结构-线性表 2020-03-28
- 线段树学习资料 2020-03-19
- 排兵布阵 2020-02-21
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash