题目传送门: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 ——————————
仔细想一想,似乎按二进制分治也可以做?