【NOI2017】泳池

题解：

满分的笛卡尔树以后再学吧。。

40分还是比较好想的

但是状态挺复杂的

直接贴代码了

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define IL inline

#define rint register ll

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

#define me(x) memset(x,0,sizeof(x))

ll n,k,x,y;

ll mo=;

ll f[][][][][][][][];

ll ans=;

void js(ll &x,ll y)

{

  x=(x+y)%mo;

}

void gcd(ll x,ll y,ll &a,ll &b)

{

  if (y==)

  {

    a=; b=; return;

  }

  gcd(y,x%y,b,a);

  b=b-a*(x/y);

}

int main()

{

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

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

  cin>>n>>k>>x>>y;

  ll x1,y1;

  gcd(y,mo,x1,y1);

  ll pp=(x*x1)%mo;

  int p[];

  p[]=;

  rep(i,,k) p[i]=(p[i-]*pp)%mo;

  rep(i,,k) p[i]=(p[i]*(1ll-pp))%mo;

  if (n==)

  {

    cout<<(p[k]%mo+mo)%mo<<endl;

    return ;

  }

  f[][][][][][][][]=;

   rep(i,,n)

  {

    ll kk=i%,tt=(i+)%;

    me(f[kk]);

    rep(i,,k)

    {

      rep(i1,,k)

      {

        if ((i1+(i>=))>k) break;

        rep(j1,,k/)

        {

          if ((j1+(i>=))*>k) break;

          rep(i2,,k/)

          {

            if ((i2+(i>=))*>k) break;

            rep(j2,,k/)

            {

              if ((j2+(i>=))*>k) break;

              rep(i3,,k/)

              {

                if ((i3+(i>=))*>k) break;

                rep(j3,,)

                {

                  if (j3==&&i>=) break;

                  rep(k1,,)

                  {

                    bool t=;

                    if ((i1+(i>=))==k) t=;

                    if ((j1+(i>=))*==k) t=;

                    if ((i2+(i>=))*==k) t=;

                    if ((j2+(i>=))*==k) t=;

                    if ((i3+(i>=))*==k) t=;

                    if (i==k) t=;

                    js(f[kk][(i>=)?i1+:][(i>=)?j1+:][(i>=)?i2+:][(i>=)?j2+:][(i>=)?i3+:][i>=][k1|t],

                    f[tt][i1][j1][i2][j2][i3][j3][k1]*p[i]);

                    int ans1=;

                    ans1++;

                  }

                }

              }

            }

          }

        }

      }

    }

  }

rep(i1,,)

  rep(j1,,)

    rep(i2,,)

      rep(j2,,)

        rep(i3,,)

          rep(j3,,)

            js(ans,f[n%][i1][j1][i2][j2][i3][j3][]);

  cout<<(ans%mo+mo)%mo<<endl;

  return ;

}