#8 //HDU 5730 Shell Necklace（CDQ分治+FFT）

Description
给出长度分别为1~n的珠子，长度为i的珠子有a[i]种，每种珠子有无限个，问用这些珠子串成长度为n的链有多少种方案

题解：

dp[i]表示组合成包含i个贝壳的项链的总方案数
转移：dp[i]=Σdp[i-j]*a[j]（1<=j<=i）

#include <bits/stdc++.h>

using namespace std;

#define dob complex<double>

#define rint register int

#define mo 313

#define IL inline

const double pi=acos(-1.0);

const int N=2e5;

dob a[N],b[N],bb[N];

int n,m,r[N],l,dp[N],sum[N];

IL void fft(dob *a,int o)

{

  for (rint i=;i<n;i++)

    if (i>r[i]) swap(a[i],a[r[i]]);

  for (rint i=;i<n;i*=)

  {

    dob wn(cos(pi/i),sin(pi*o/i)),x,y;

    for (rint j=;j<n;j+=(i*))

    {

      dob w(,);

      for (rint k=;k<i;k++,w*=wn)

      {

        x=a[j+k],y=w*a[i+j+k];

        a[j+k]=x+y,a[i+j+k]=x-y;

      }

    }

  }

}

IL void query()

{

  l=;

  for (n=;n<=m;n<<=) l++;

  for (rint i=;i<n;i++) r[i]=(r[i/]/)|((i&)<<(l-));

  fft(a,); fft(b,);

  for (rint i=;i<n;i++) a[i]*=b[i];

  fft(a,-);

  for (rint i=;i<=m;i++)

    sum[i]=a[i].real()/n+0.5,sum[i]%=mo;

}

#define mid (l+r)/2

void cdq(int l,int r)

{

  if (l==r) return;

  cdq(l,mid);

  for (rint i=l;i<=mid;i++) a[i-l]=dp[i];

  m=r-l;

  rint x;

  for (x=;x<=m;x<<=);

  for (rint i=mid+;i<=l+x;i++) a[i-l]=;

  b[]=;

  for (rint i=;i<=x;i++) b[i]=bb[i];

  query();

  for (rint i=mid-l+;i<=r-l;i++)

    {

      dp[i+l]+=sum[i];

      dp[i+l]%=mo;

    }

  cdq(mid+,r);

}

int main()

{

  freopen("noi.in","r",stdin);

  freopen("noi.out","w",stdout);

  std::ios::sync_with_stdio(false);

  int k;

  while (cin>>k&&k)

  {

    for (rint i=;i<=k;i++) cin>>bb[i];

    memset(dp,,sizeof(dp));

    dp[]=;

    cdq(,k);

    cout<<dp[k]%mo<<endl;

  }

  return ;

}

该改一个fft模板了，实在是慢https://www.luogu.org/record/show?rid=3767323

巴特西

#8 //HDU 5730 Shell Necklace（CDQ分治+FFT）

最新文章

热门文章