【NOI2017】泳池

时间:2021-01-14 06:51:40

题解:

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

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 ;
}