1977: Bit-reversal Permutation(반복)

1977: Bit-reversal Permutation Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 7 Solved: 3 Description A fast Fourier transform (FFT) algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IFFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from O(n2), which arises if one simply applies the definition of DFT, to O(nlogn), where n is the data size.

                                                                                                                                                                               ——From Wikipedia

During this summer holiday, csuxushu feels so bored to learn FFT. Because FFT is a complicated algorithm, he need to apply a bit-reversal permutation to a sequence first before DFT which is a part of FFT.
In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n = 2^k is a power of two. It is defined by indexing the elements of the sequence by the numbers from 0 to n − 1 and then reversing the binary representations of each of these numbers (padded so that each of these binary numbers has length exactly k). Each item is then mapped to the new position given by this reversed value.
Because all fellows in CSU(California State University ) can apply FFT, NTT or even FWT, it is a shame that he even doesn’t know how to take the first step. As one of the best computer programmer in CSU, can you help him?
You may think this problem is too hard to solve. In fact, it is a piece of cake to you. Remember to see the hint :-)
Input The first line of the input gives the number of test cases T(T≤10); T test cases follow.Each test case contains a number sequence. In each case, the first line is a number N(1≤N≤10^5), the number of elements in the following sequence.The second line is the sequence.Its length may not be exactly a power of two, so you can append some zeros to make it the minimal power of two larger than or equal to N.
Output For each test case, output the sequence from input in bit-reversal order.
Sample Input 1 6 21 58 96 12 45 65 Sample Output 21 45 96 0 58 65 12 0 Hint Bit-reverse Order 중국어 힌트: 우리가 최종적으로 처리한 계수는 왼쪽에서 오른쪽의 번호의 이진 형식은 각각 000100010110101111이고 이진 순서를 반순으로 하면 00000101100111001010101010101110111111을 얻을 수 있다. 이 반순으로 된 이진 코드는 작은 것에서 큰 것으로 배열된다.즉, 우리는 각 아래에 표시된 이진 인코딩에 따라 처리 계수의 순서를 확정할 수 있다.이런 방법을 비트리버스터치환(Bit-reversal permutation)이라고 한다.
Source 2017년 8월 월간경기.
Author 서수
원제 주소:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1977

제목:

시뮬레이션 FFT, FWT, NTT 같은 연산의 핵심 분치 사상은 짝수 아래에 왼쪽 구간을 표시하고 홀수 오른쪽을 표시한다. 2의 전체 멱이 아니라 2의 전체 멱을 보충해야 하기 때문에 공간은 두 배로 열어야 한다.
직접 시뮬레이션할 수도 있고 밑에 표시된bit에 대해reverse를 하고 결과에 따라sort를 갈 수도 있어요.

#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
int n,m,a[maxn],b[maxn]; 

inline void divd(int l,int r)
{
  if(l>=r)return ;
  int mid=(l+r)>>1;
  int L=l-1,R=mid;
  for(int i=l;i<=r;++i)
  if(i&1)b[++L]=a[i];
  else b[++R]=a[i];

  for(int i=l;i<=r;++i)a[i]=b[i];
  divd(l,mid);
  divd(mid+1,r);
}

int main()
{
  int T;
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(m=1;m1);
    for(int i=n+1;i<=m;++i)a[i]=0;
    divd(1,m);
    for(int i=1;iprintf("%d ",a[i]);
    printf("%d
",a[m]);
  }
  return 0;
}