【SOJ 1718】特工

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/08/216378216437812.png
题解传送门：http://oi.cyo.ng/wp-content/uploads/2016/08/123478756.png
OJ传送门：http://oi.cdshishi.net:8080/Problem/1718

考试的时候，看一眼数据范围
马上反应过来开是FFT，而且坚信是FFT
结果后来没想出来，考完试还被lcr给D了………
结果最后一看，真™是FFT!

这个题，看一眼马上想到高斯消元
于是考试的时候就写了O(n^3)的高斯消元

后来讲题的时候，说到其实就是一个矩阵求逆，我很赞同
于是就来补O(n^3)的矩阵求逆啦！

#include<iostream>
#include<cstdio>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MAXN = 3000;
const double EPS = 1e-8;

int n;
double mat[MAXN*2][MAXN],vout[MAXN],arr[MAXN];

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define lowbit(x) ((x)&-(x))
inline int bitcount(int w){
	int ret = 0;
	while (w) ret++, w -= lowbit(w);
	return ret;
}

int LCA(int a, int b){
	if (!b) return a;
	else return LCA(b,a%b);
}

inline void Get_Reverse_Matrix(){
	for (int i=1,w;i<=n;i++) {
		for (w=i;w<=n;w++) if (mat[i+n][w]) break;
		for (int j=1;j<=n*2;j++) swap(mat[j][w], mat[j][i]);
		if (abs(mat[i+n][i]) < EPS) continue;
		else for (int j=1;j<=n;j++) if (abs(mat[i+n][j]) > EPS && j != i) {
			double tmp = mat[i+n][j]/mat[i+n][i];
			for (int k=1;k<=n*2;k++) mat[k][j] -= mat[k][i]*tmp;
		}
		double tmp = mat[i+n][i];
		for (int j=1;j<=n*2;j++) mat[j][i] /= tmp;
	}
}

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) arr[i] = read();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) 
		mat[i+n][j] = (bitcount((i-1|j-1)^i-1)+1) % 2;
	for (int i=1;i<=n;i++) mat[i][i] = 1;
	Get_Reverse_Matrix();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) 
		vout[i] += mat[i][j]*arr[j];
	for (int i=1;i<=n;i++) printf("%d ",(int)(vout[i]+EPS));
	return 0;
}

std是应用数据特点，把矩阵求逆给搞到了O(n^logn)
我就不写程序啦，反正SOJ代码可以看

—————————— UPD 2017.7.3 ——————————
仔细想一想，似乎按二进制分治也可以做？