总结:
D1T1T2的思路较为好想,D1T3考试时估计是战略放弃的对象,D2T1思路容易卡在优化状态上(虽然明显3n的状态中有很多无用状态,从而想到子集最优,选择子集最优容易发现反例,从而考虑连带周边一起考虑,去年考场上想出来的,今年却想不出来***)但50十分容易,D2T2的式子超出目前水平(多项式的式子推法需要继续加强),D2T3在学过MinMax容斥以及树上高斯消元(好像还需要FWT)后较为简单,目前水平在250-380中来回飘荡,感觉pkuwc2019要完。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define X first
#define Y second
#define N 300005
#define P 998244353
struct st{int l,r,v,tg;}T[N*];
int n,cc,tt,ans,p[N],d[N],ch[N][],rt[N];
pair<int,int>q[N];
int pw(int a,int b){int r=;for(;b;b>>=,a=1ll*a*a%P)if(b&)r=1ll*r*a%P;return r;}
int sqr(int x){return 1ll*x*x%P;}
void down(int x)
{
if(T[x].tg!=)
{
T[T[x].l].tg=1ll*T[T[x].l].tg*T[x].tg%P;
T[T[x].l].v=1ll*T[T[x].l].v*T[x].tg%P;
T[T[x].r].tg=1ll*T[T[x].r].tg*T[x].tg%P;
T[T[x].r].v=1ll*T[T[x].r].v*T[x].tg%P;
T[x].tg=;
}
}
void upd(int &x,int l,int r,int p)
{
x=++cc;T[x].v=T[x].tg=;
if(l==r)return;
int mid=l+r>>;
if(p<=mid)upd(T[x].l,l,mid,p);else upd(T[x].r,mid+,r,p);
}
int merge(int x,int y,int p,int pl1,int pl2,int pr1,int pr2)
{
if(!x&&!y)return ;
if(x&&!y)
{
int q=(P+-p),r=(1ll*p*pl2+1ll*q*pr2)%P;
T[x].v=1ll*T[x].v*r%P;
T[x].tg=1ll*T[x].tg*r%P;
return x;
}
if(!x&&y)
{
int q=(P+-p),r=(1ll*p*pl1+1ll*q*pr1)%P;
T[y].v=1ll*T[y].v*r%P;
T[y].tg=1ll*T[y].tg*r%P;
return y;
}
down(x);down(y);
int r1=T[T[x].r].v,r2=T[T[y].r].v,r3=T[T[x].l].v,r4=T[T[y].l].v;
T[x].l=merge(T[x].l,T[y].l,p,pl1,pl2,(pr1+r1)%P,(pr2+r2)%P);
T[x].r=merge(T[x].r,T[y].r,p,(pl1+r3)%P,(pl2+r4)%P,pr1,pr2);
T[x].v=(T[T[x].l].v+T[T[x].r].v)%P;return x;
}
void dfs(int x)
{
if(d[x]==)return;
if(d[x]==){dfs(ch[x][]);rt[x]=rt[ch[x][]];return;}
dfs(ch[x][]);dfs(ch[x][]);
rt[x]=merge(rt[ch[x][]],rt[ch[x][]],p[x],,,,);
}
void qry(int x,int l,int r)
{
if(!x)return;
if(l==r){ans=(ans+1ll*l*q[l].X%P*sqr(T[x].v))%P;return;}
int mid=l+r>>;down(x);qry(T[x].l,l,mid);qry(T[x].r,mid+,r);
}
int main()
{
scanf("%d",&n);
for(int i=,fa;i<=n;i++)scanf("%d",&fa),ch[fa][d[fa]++]=i;
int iv=pw(,P-);
for(int i=;i<=n;i++)scanf("%d",&p[i]);
for(int i=;i<=n;i++)if(!d[i])q[++tt]=make_pair(p[i],i);else p[i]=1ll*p[i]*iv%P;
sort(q+,q+tt+);
for(int i=;i<=tt;i++)upd(rt[q[i].Y],,tt,i);
dfs();qry(rt[],,tt);printf("%d\n",ans);
return ;
}
loj#2538. 「PKUWC2018」Slay the Spire
#include<bits/stdc++.h>
using namespace std;
#define N 3005
#define mod 998244353
int n,m,k,a[N],b[N],f[N][N],g[N][N],s[N],C[N][N];
bool cmp(int a,int b){return a>b;}
int calcf(int a,int b)
{
if(!b)return C[n][a];
int r=;
for(int i=;i<=n;i++)(r+=1ll*f[b][i]*C[n-i][a-b]%mod)%=mod;
return r;
}
int calcg(int a,int b)
{
if(!b)return ;
int r=;
for(int i=;i<=n;i++)(r+=1ll*g[b][i]*C[n-i][a-b]%mod)%=mod;
return r;
}
int main()
{
for(int i=;i<=;i++)C[i][]=;
for(int i=;i<=;i++)for(int j=;j<=i;j++)C[i][j]=(C[i-][j]+C[i-][j-])%mod;
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)scanf("%d",&b[i]);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
sort(b+,b+n+,cmp);sort(a+,a+n+,cmp);
s[]=;
for(int i=;i<=n;i++)f[][i]=b[i],s[i]=(s[i-]+f[][i])%mod;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)f[i][j]=1ll*b[j]*s[j-]%mod;
for(int j=;j<=n;j++)s[j]=(s[j-]+f[i][j])%mod;
}
for(int i=;i<=n;i++)g[][i]=a[i],s[i]=(s[i-]+g[][i])%mod;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)g[i][j]=(1ll*a[j]*C[j-][i-]+s[j-])%mod;
for(int j=;j<=n;j++)s[j]=(s[j-]+g[i][j])%mod;
}
int ans=;
for(int i=;i<=n&&i<=m;i++)
{
int j=m-i;if(j>n)continue;
if(i<k)(ans+=1ll*calcf(i,i)*calcg(j,k-i)%mod)%=mod;else (ans+=1ll*calcf(i,k-)*calcg(j,)%mod)%=mod;
}
printf("%d\n",ans);
}
return ;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=,P=;
int n,m,nn,mx[N],sz[N],e[],f[N],fac[],ifac[];
int pw(int a,int b){int r=;for(;b;b>>=,a=1ll*a*a%P)if(b&)r=1ll*r*a%P;return r;}
int A(int a,int b){return 1ll*fac[a]*ifac[a-b]%P;}
int main()
{
scanf("%d%d",&n,&m);nn=(<<n);
for(int i=,u,v;i<=m;i++)scanf("%d%d",&u,&v),u--,v--,e[u]|=(<<v),e[v]|=(<<u);
for(int i=;i<n;i++)e[i]|=(<<i);
for(int i=fac[]=;i<=;i++)fac[i]=1ll*fac[i-]*i%P;
ifac[]=pw(fac[],P-);
for(int i=;i;i--)ifac[i-]=1ll*ifac[i]*i%P;
for(int i=;i<nn;i++)for(int j=;j<n;j++)if(i>>j&)sz[i]++;
f[]=;
for(int i=;i<nn;i++)if(f[i])for(int j=;j<n;j++)if(!(i>>j&))
{
int t=i|e[j];
if(mx[t]<mx[i]+)f[t]=,mx[t]=mx[i]+;
if(mx[t]==mx[i]+)f[t]=(f[t]+1ll*f[i]*A(n-sz[i]-,sz[e[j]]-sz[i&e[j]]-))%P;
}
int ans=1ll*f[nn-]*ifac[n]%P;
printf("%d\n",ans);
return ;
}
#include<bits/stdc++.h>
using namespace std;
const int N=,mod=;
int n,ans,w[N],sum[N],f[N],r[N];
int pw(int a,int b){int r=;for(;b;b>>=,a=1ll*a*a%mod)if(b&)r=1ll*r*a%mod;return r;}
void ntt(int n,int *a,int f)
{
int l=;while((<<l)<n)l++;
for(int i=;i<n;i++)r[i]=(r[i>>]>>)|((i&)<<(l-));
for(int i=;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
for(int i=;i<=n;i<<=)
{
int wn=pw(,(mod-)/i);
if(f==-)wn=pw(wn,mod-);
for(int j=;j<n;j+=i)for(int k=,w=;k<(i>>);k++,w=1ll*w*wn%mod)
{
int u=a[j+k],v=1ll*a[j+k+(i>>)]*w%mod;
a[j+k]=(u+v)%mod;a[j+k+(i>>)]=(u+mod-v)%mod;
}
}
if(f==-)for(int i=,iv=pw(n,mod-);i<n;i++)a[i]=1ll*a[i]*iv%mod;
}
int gt(int L,int R)
{
int l=L,r=R,mid;
while(l<=r)
{
mid=l+r>>;
if(sum[mid]-sum[L-]<=sum[R]-sum[mid])l=mid+;else r=mid-;
}
return mid==R?mid-:mid;
}
void sol(int l,int r,int *f)
{
if(l==r){f[]=;f[w[l]]=mod-;return;}
int mid=gt(l,r);
int n=sum[r]-sum[l-],nn=;
while(nn<=*n)nn<<=;
int *a=new int[nn|],*b=new int[nn|];
sol(l,mid,a);sol(mid+,r,b);
ntt(nn,a,);ntt(nn,b,);
for(int i=;i<nn;i++)a[i]=1ll*a[i]*b[i]%mod;
ntt(nn,a,-);
for(int i=;i<nn;i++)f[i]=a[i];
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&w[i]);
sort(w+,w+n+);
for(int i=;i<=n;i++)sum[i]=sum[i-]+w[i];
sol(,n,f);
for(int i=;i<=sum[n];i++)ans=(ans+1ll*f[i]*w[]%mod*pw(w[]+i,mod-)%mod)%mod;
printf("%d\n",ans);
return ;
}
#include<bits/stdc++.h>
using namespace std;
const int N=,mod=;
int n,Q,S,d[N],id[N],a[N],b[N],mn[<<|],sz[<<|],mx[<<|];
vector<int>g[N];
int pw(int a,int b){int r=;for(;b;b>>=,a=1ll*a*a%mod)if(b&)r=1ll*r*a%mod;return r;}
void dfs(int x,int p,int msk)
{
if(msk>>(x-)&){a[x]=b[x]=;return;}
int sa=,sb=;
for(int i=;i<g[x].size();i++)if(g[x][i]!=p)dfs(g[x][i],x,msk),sa=(sa+a[g[x][i]])%mod,sb=(sb+b[g[x][i]])%mod;
int c=pw(+mod-1ll*sa*id[x]%mod,mod-);
a[x]=1ll*id[x]*c%mod;b[x]=1ll*(+1ll*sb*id[x]%mod)*c%mod;
}
int main()
{
scanf("%d%d%d",&n,&Q,&S);
for(int i=,u,v;i<n;i++){scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);d[u]++;d[v]++;}
for(int i=;i<=n;i++)id[i]=pw(d[i],mod-);
int nn=<<n;
for(int i=;i<nn;i++)sz[i]=sz[i>>]^(i&);
for(int i=;i<nn;i++){dfs(S,,i);mn[i]=1ll*(sz[i]?:mod-)*b[S]%mod;}
for(int i=;i<nn;i++)mx[i]=mn[i];
for(int i=;i<n;i++)for(int j=;j<nn;j++)if(!(j>>i&))(mx[j|(<<i)]+=mx[j])%=mod;
while(Q--)
{
int k,msk=;scanf("%d",&k);
for(int i=,x;i<k;i++)scanf("%d",&x),msk|=(<<(x-));
printf("%d\n",mx[msk]);
}
return ;
}
PKUWC2018 5/6的更多相关文章
-
PKUWC2018游记
PKUWC2018游记 Day -inf 从去年的12月底开始停课,到现在也有整整一个月的时间了. 前两周考的是OI赛制,后来就变成了IOI赛制. 整体上考的很炸,虐场的次数远少于被虐的次数. 关于去 ...
-
PKUWC2018划水记
PKUWC2018划水记 Day -1 从福州出发去长沙,原本是预定Day0当天的航班,后来怕来不及提前到了今天. 由于最近长沙下雪,所以听说飞机取消了很多班次,所以早上起来的时候还特地看了一 ...
-
Loj #2542. 「PKUWC2018」随机游走
Loj #2542. 「PKUWC2018」随机游走 题目描述 给定一棵 \(n\) 个结点的树,你从点 \(x\) 出发,每次等概率随机选择一条与所在点相邻的边走过去. 有 \(Q\) 次询问,每次 ...
-
【LOJ#2542】[PKUWC2018]随机游走(min-max容斥,动态规划)
[LOJ#2542][PKUWC2018]随机游走(min-max容斥,动态规划) 题面 LOJ 题解 很明显,要求的东西可以很容易的进行\(min-max\)容斥,那么转为求集合的\(min\). ...
-
题解-PKUWC2018 Minimax
Problem loj2537 Solution pkuwc2018最水的一题,要死要活调了一个多小时(1h59min) 我写这题不是因为它有多好,而是为了保持pkuwc2018的队形,与这题类似的有 ...
-
「PKUWC2018」随机游走(min-max容斥+FWT)
「PKUWC2018」随机游走(min-max容斥+FWT) 以后题目都换成这种「」形式啦,我觉得好看. 做过重返现世的应该看到就想到 \(min-max\) 容斥了吧. 没错,我是先学扩展形式再学特 ...
-
LOJ2542 PKUWC2018 随机游走 min-max容斥、树上高斯消元、高维前缀和、期望
传送门 那么除了D1T3,PKUWC2018就更完了(斗地主这种全场0分的题怎么会做啊) 发现我们要求的是所有点中到达时间的最大值的期望,\(n\)又很小,考虑min-max容斥 那么我们要求从\(x ...
-
「PKUWC2018」猎人杀
「PKUWC2018」猎人杀 解题思路 首先有一个很妙的结论是问题可以转化为已经死掉的猎人继续算在概率里面,每一轮一直开枪直到射死一个之前没死的猎人为止. 证明,设所有猎人的概率之和为 \(W\) , ...
-
【LOJ2541】【PKUWC2018】猎人杀(容斥,FFT)
[LOJ2541][PKUWC2018]猎人杀(容斥,FFT) 题面 LOJ 题解 这题好神仙啊. 直接考虑概率很麻烦,因为分母总是在变化. 但是,如果一个人死亡之后,我们不让他离场,假装给他打一个标 ...
随机推荐
-
ubuntu14.04换一个更快的源
mirrors.yun-idc.com,这个源可比ubuntu自带的源快多了,我的source.list文件内容如下: deb http://mirrors.yun-idc.com/ubuntu/ t ...
-
curl Protocol &#39;http not supported or disabled in libcurl
C:\Documents and Settings\ganiks.liu\Desktop\curl-7.37.0-win32\bin>curl -V curl 7.37.0 (i386-pc-w ...
-
id为194024的进程当前未运行
.NET MVC 编译运行时 提示 >> id为194024的进程当前未运行 << 清理解决方案,重新运行
-
Python入门(二)列表、字典、字符串、元组、集合
列表list什么是列表:Python内置的一种数据类型是列表,list是一种有序的集合,可以随时添加和删除其中的元素 创建List列表的方法 L = ['杨俊辰',‘啦啦啦’,'Tom'] empty ...
-
D - The Lucky Week ZOJ - 3939 (思维)
题目链接: D - The Lucky Week ZOJ - 3939 题目大意:幸运的星期指,星期一为每个月的1 or 11 or 21号.给出第一个幸运星期的时间,问从当前的日起开始.第n个的日 ...
-
6、Spring-Kafka4
4.1. Using Spring for Apache Kafka This section offers detailed explanations of the various concerns ...
-
48-Python 安装pyautogui失败解决办法
转载自:https://www.cnblogs.com/SH170706/p/9809830.html Python 安装pyautogui 在Python中使用PyAutoGui模拟键盘和鼠标操作 ...
-
软考之信息安全工程师(包含2016-2018历年真题详解+官方指定教程+VIP视频教程)
软考-中级信息安全工程师2016-2018历年考试真题以及详细答案,同时含有信息安全工程师官方指定清华版教程.信息安全工程师高清视频教程.持续更新后续年份的资料.请点赞!!请点赞!!!绝对全部货真价实 ...
-
java基础篇之HashMap
HashMap和C#中的Dictionary基本一样 键是唯一值 值可以是对象 循环HashMap的方式:一: 1,通过Set<T> st = hs.keySet()找到所有的key值集合 ...
-
CKEditor插件开发
以前做过一个教育项目,是有关在线考试的.其中对编辑器CKEditor做了扩充,增加了插入客观题.主观题.选择题和判断题的功能.这里记述下CKEditor插件开发的过程. CKEditor以前叫FCKE ...