codeforces736D. Permutations(线性代数)
2024-08-30 10:08:05
题意
$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 = ;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int N, M;
bitset<MAXN * + > b[MAXN];
int x[], y[];
int main() {
N = read(); M = read();
for(int i = ; i <= N; i++) b[i][i + N] = ;
for(int i = ; i <= M; i++) {
x[i] = read(), y[i] = read();
b[x[i]][y[i]] = ;
}
for(int i = , j; i <= N; i++) {
for(j = i; j <= N; j++) if(b[j][i]) {swap(b[i], b[j]); break;}
for(int k = ; k <= N; k++)
if(b[k][i] && (k != i)) b[k] ^= b[i];
}
for(int i = ; i <= N; i++, puts(""))
for(int j = ; j <= * N; j++)
cout << b[i][j] << " ";
return ;
}
/*
3 7
1 1
1 3
2 2
2 3
3 1
3 2
3 3 */
最新文章
- 第一章-第十四题(Hello world程序)
- Maven+Spring MVC Spring Mybatis配置
- MVC文件夹
- C#中窗体的互相访问
- druid报异常 “sql injection violation, part alway true condition not allow”的解决方案
- Symfony2 EventDispatcher组件
- Codeforces Round #372 (Div. 2) C 数学
- QProcess 进程类—调用外部程序
- 【firefox】关闭firefox缓存
- 多线程校验url的种种。。。
- Redisson碰到的问题
- MySQL(1)---索引
- Python-正则复习-56
- Python使用@property装饰类方法
- Qt 编程指南 2 Hello Designer
- 【ML】ICLR2016_Delving Deeper into Convolutional Networks
- Appium 连手机失败Error: Android bootstrap socket crashed: Error: getaddrinfo ENOTFOUND localhost undefined:4724
- JS-缓冲运动基础结构
- CSS单位分析
- API接口测试中需要注意的地方
热门文章
- python 基础之第五天
- [WC 2006] 水管局长
- 利用openssl进行base64的编码与解码
- Ubuntu 安装indicator-sysmonitor
- project工期出现小数问题
- error:: undefined reference to symbol &#39;__glewBufferSubData&#39; 未定义的引用 以及 error: main.o: undefined reference to symbol &#39;glTexImage2D&#39;
- 51nod1181【素数筛】
- 51nod1402(贪心)
- 2014-9-9 NOIP模拟赛
- adb server version (39) doesn&#39;t match this client (40); killing...