## 【SOJ 1718】特工

#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];

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(){
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)

—————————— UPD 2017.7.3 ——————————