6.11 冲刺国赛模拟 16
T3 多边形
凸多边形说明合法方案中同一种向量必须连续且多种顺序只算一个，因此直接计算各个向量选择的个数。
设第 \(i\) 个向量选了 \(c_i\) 个，按照两个方向的正负分，可以写作：
\(y\) 类似。
于是相当于构造出的方案要满足四个数都 \(\le m\)，可以数位 DP，按位枚举 \(c\)，在每一位上枚举的复杂度是 \(O(2^n)\)，注意到这里是有 \(|x|,|y|\le \omega=4\) 的，因此可能有进位，只能从低位到高位，设 \(f(i,px,py,nx,ny,limx,limy)\) 表示枚举到 \(2^i\) 位，当前在 \(2^i\) 位的值分别为 \(px,py,nx,ny\)，当前 \(x,y\) 是否卡上界（\(\le m\) 的条件）状态数是 \(O((n\omega)^42^n\log m)\)，这也是复杂度。
(赛时的想法是找互质的然后按照相似来求，和正解偏差很大，数位 DP 可以这样使用也蛮高级的）
点击查看代码
int n,m;
int x[maxn],y[maxn];
int f[maxlog][maxw][maxw][maxw][maxw][2][2];
bool vis[maxlog][maxw][maxw][maxw][maxw][2][2];
int dfs(int now,int x1,int x2,int y1,int y2,bool limx,bool limy){
if(now==30) return !x1&&!x2&&!y1&&!y2&&limx&&limy;
if(vis[now][x1][x2][y1][y2][limx][limy]) return f[now][x1][x2][y1][y2][limx][limy];
vis[now][x1][x2][y1][y2][limx][limy]=true;
int res=0;
for(int s=0;s<(1<<n);++s){
int tmpx1=x1,tmpx2=x2,tmpy1=y1,tmpy2=y2;
for(int i=1;i<=n;++i){
if(s&(1<<i-1)){
if(x[i]>0) tmpx1+=x[i];
else tmpx2-=x[i];
if(y[i]>0) tmpy1+=y[i];
else tmpy2-=y[i];
}
}
if((tmpx1^tmpx2)&1||(tmpy1^tmpy2)&1) continue;
bool chkm=(m>>now)&1,chkx=tmpx1&1,chky=tmpy1&1;
res=(res+dfs(now+1,tmpx1/2,tmpx2/2,tmpy1/2,tmpy2/2,chkm?(!chkx||limx):(!chkx&&limx),chkm?(!chky||limy):(!chky&&limy)))%mod;
}
return f[now][x1][x2][y1][y2][limx][limy]=res;
}
int ans;
int main(){
freopen("polygon.in","r",stdin);
freopen("polygon.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i){
x[i]=read(),y[i]=read();
}
ans=(dfs(0,0,0,0,0,true,true)-1+mod)%mod;
printf("%d\n",ans);
return 0;
}
6.12 冲刺国赛模拟 17
T1 掌分治
树上操作很经典，考虑枚举点对 \((u,v)\) 计算删除 \(u\) 时 \((u,v)\) 连通的概率，求和就是答案的期望，在树上这个概率就是 \(\dfrac{1}{\mathrm{dist}(u,v)}\)。
放在一个环上，设 \(u\to v\) 两条路径的点数分别是 \(a,b\)，那么只需要保证其中一条没被删除就行了，同时都没被删除需要容斥一下，答案就是 \(\dfrac{1}{a}+\dfrac{1}{b}-\dfrac{1}{a+b-1}\)，这里考场上想的是枚举这些点中 \(u\) 删的时刻再累加，就不太好拓展了。
放在仙人掌上，先建出圆方树，考虑多个环和链结合起来的答案容斥部分并非简单的相乘，考虑固定前面走法不变，长度为 \(l\)，增加一个环，此时产生影响是 \(\dfrac{1}{l+a}+\dfrac{1}{l+b}-\dfrac{1}{l+a+b-1}\)，因此增加一个环后这些分母增加，而分母一定在 \([1,n]\) 内，考虑 DP 系数，转移类似背包。由于合并多个环可能相交部分点被算两次，所以钦定当前的环长度不算方点父亲，最终平移一位就行。
做 \(n\) 次不同位置出发，复杂度 \(O(n^3)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=405;
const int mod=998244353;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int n,m;
int inv[maxn];
struct edge{
int to,nxt;
}e[maxn<<2];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int dfn[maxn],low[maxn],dfncnt;
int st[maxn],top;
int tot;
vector<int> E[maxn<<1];
unordered_map<int,int> mp[maxn];
void Tarjan(int u){
dfn[u]=++dfncnt,low[u]=dfn[u];
st[++top]=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
++tot;
int id=0;
while(st[top]!=v){
E[st[top]].push_back(tot),E[tot].push_back(st[top]);
mp[tot-n][st[top]]=++id;
--top;
}
E[v].push_back(tot),E[tot].push_back(v);
mp[tot-n][v]=++id;
--top;
E[u].push_back(tot),E[tot].push_back(u);
mp[tot-n][u]=++id;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int f[maxn][maxn];
void dfs(int u,int fa){
if(u<=n){
f[u][0]=1;
for(int v:E[u]){
if(v==fa) continue;
dfs(v,u);
}
}
else{
if((int)E[u].size()==2){
for(int v:E[u]){
if(v==fa) continue;
dfs(v,u);
for(int i=0;i+1<n;++i) f[fa][i+1]=(f[fa][i+1]+f[v][i])%mod;
}
}
else{
int id=mp[u-n][fa];
int now=0;
for(int v:E[u]){
++now;
if(v==fa) continue;
dfs(v,u);
int k1=abs(now-id),k2=(int)E[u].size()-k1;
for(int i=0;i+k1<n;++i) f[fa][i+k1]=(f[fa][i+k1]+f[v][i])%mod;
for(int i=0;i+k2<n;++i) f[fa][i+k2]=(f[fa][i+k2]+f[v][i])%mod;
for(int i=0;i+k1+k2-1<n;++i) f[fa][i+k1+k2-1]=(f[fa][i+k1+k2-1]-f[v][i]+mod)%mod;
}
}
}
}
int ans;
int main(){
freopen("cactus.in","r",stdin);
freopen("cactus.out","w",stdout);
n=read(),m=read();
inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=m;++i){
int u=read(),v=read();
add_edge(u,v);
}
tot=n;
Tarjan(1);
for(int i=1;i<=n;++i){
memset(f,0,sizeof(f));
dfs(i,0);
for(int j=0;j<n;++j) ans=(ans+1ll*f[i][j]*inv[j+1]%mod+mod)%mod;
}
printf("%d\n",ans);
return 0;
}