cafelier@SRM

SRM436 1000

あとで | 12:28 |

通った。そうかどっちか逆転しないと

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <complex>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

CMP tmp[65536*2];

template<int F>
void fft_impl( CMP a[], int n, int stride = 1 )
{
  if( n > 1 )
  {
    CMP *ev=a, *od=a+stride;
    int s2=stride*2, n2=n/2;

    fft_impl<F>( ev, n2, s2 );
    fft_impl<F>( od, n2, s2 );

    for(int i=0; i<n; ++i) tmp[i] = ev[i%n2*s2] + od[i%n2*s2]*polar(1.0, F*2*M_PI*i/n);
    for(int i=0; i<n; ++i) a[i*stride] = tmp[i];
  }
}

void fft( vector<CMP>& a )
{
  fft_impl<+1>(&a[0], a.size());
}

void ifft( vector<CMP>& a )
{
  fft_impl<-1>(&a[0], a.size());
  for(int i=0; i<a.size(); ++i)
    a[i] /= a.size();
}

class CircularShifts {
public:
  int maxScore(int N, int Z0, int A, int B, int M) 
  {
    // input
    LL X[60000], Y[60000], Z=Z0%M;
    for(int i=0; i<N+N; ++i)
    {
      (i<N ? X[i] : Y[i-N]) = Z % 100;
      Z = (Z*A+B) % M;
    }

    // solve
    int NN = 1;
    while( NN < N*2 ) NN*=2;

    vector<CMP> CX(NN), CY(NN), CZ(NN);
    for(int i=0; i<N; ++i)
      CX[i]=CX[i+N]=X[N-i-1], CY[i]=Y[i];

    fft(CX);
    fft(CY);
    transform( CX.begin(), CX.end(), CY.begin(), CZ.begin(), multiplies<CMP>() );
    ifft(CZ);

    double m = 0;
    for(int i=0; i<NN; ++i)
      m = max(m, CZ[i].real());
    return int(m+0.5);
  }
};