考试总结：这次考试，我非常真实地感觉到了自己能力的提高，具体来说，在之前的考试中，读完题之后我只会想到暴力的思路，甚至有的题连暴力都打不出来，但是这次在考场上我已经有了自己的一些想法，有了一个深入思考的过程，自己演算，推式子也写了几张草稿纸，对于测试点的部分分也有了一定的把握。在改题的时候，我基本上都是研究下发的题解自己该出来的，总之，这几次考试我的收获很大，所有的付出都是值得的。
T1 玩具
思路：我们模拟一下操作过程，那么很显然，最终得到的应该是一颗树，那么如果我们不看 1 结点，那么应该是一个森林，这道题是个 dp,我们设i个点的森林，有j个点在第一颗树的概率\(dp_{i,j}=dp_{i-1,j-1}\times(j-1)\times(inv_i)+dp_{i-1,j}\times(i-j)\times(inv_i)\)设第一棵树有i 个点，深度不超过j的概率 \(f_{i,j}=g_{i-1,j-1}\),设有i个点的森林，深度不超过j的概率 \(g_{i,j}=\sum\limits_{k=1}^{i}f_{k,j}\times g_{i-k,j}\times {dp_{i,k}}\),这个方程式比较好理解，可以结合画图理解，那么注意细节问题就是在转移的时候，我们可以用刷表法，即用当前的更新后面的，还要注意当前枚举不到的状态要在当前转移过去v，具体实现见代码：
AC_Code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=210;
long long n,p,ans;
int inv[N],g[N][N],f[N][N],dp[N][N];
ii read()
{
int x=0,f=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)
{
if(ch==‘-‘)
f=0;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return (f)?x:(-x);
}
#undef int
int main()
{
/*
i个点的森林，有j个点在第一颗树的概率
dp[i][j]=dp[i-1][j-1]*(j-1)*inv[i]+dp[i-1][j]*(i-j)*inv[i];//拿出j-1个，加上拿另外的 i-j个
i个点的树，深度不超过j的概率
f[i][j]=g[i-1][j-1]//画图显然
i个点的森林，深度不超过j的概率
g[i][j]=sum[k=1 ->i] f[k][j]*g[i-k][j]*dp[i][k];
*/
#define int long long
n=read();
p=read();
inv[1]=1;
for(re i=2;i<=n;i++)
{
inv[i]=(p-(p/i))*inv[p%i]%p;
}
dp[1][1]=1;
for(re i=2;i<=n;i++)
{
for(re j=1;j<=i;j++)
{
dp[i][j]=(dp[i-1][j-1]%p*(j-1)%p*inv[i]+dp[i-1][j]%p*(i-j)%p*inv[i])%p;
}
}
for(re i=0;i<=n;i++)
{
g[0][i]=1;
f[1][i]=1;
}
for(re i=1;i<=n;i++)
{
for(re j=0;j<i;j++)
{
for(re k=1;k<=i;k++)
g[i][j]=(g[i][j]%p+f[k][j]%p*g[i-k][j]%p*dp[i][k]%p+p)%p;
f[i+1][j+1]=g[i][j];
for(re k=j+1;k<=n;k++)
f[i+1][k]=f[i+1][j+1];
}
for(re k=i;k<=n;k++)
g[i][k]=g[i][i-1];
}
for(re i=1;i<n;i++)
ans=(ans%p+i*(f[n][i]-f[n][i-1]+p)%p)%p;
printf("%lld\n",ans);
return 0;
}
T2 y
思路：显然是一个状压dp,我们设 \(f_{i,j,s}\)表示当前走了 i 步，终点为 j,当前状态为 S 是否可以达到，
那么\(f_{i+1,to[j],s<<1|val[k]}|=f_{i,j,s}\),因为时间和空间的限制，我们直接枚举所有点转移会 T飞，所以我们考虑枚举路径的中点，正着作一遍dp,倒着做一遍dp,同时记录每个点作为中点时的状态，最后输出即可。
注意细节:我们存储状态的时候一定要最后单独开一个for循环，不要在计算的过程中存储，否则直接T飞
AC_Code
#include<bits/stdc++.h>
#define re register int
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
#define ii inline int
#define iv inline void
#define head heaaaddddd
#define next netyurywi
using namespace std;
const int N=1e4+10;
int n,m,d,tot;
long long ans=0;
int to[N<<1],next[N<<1],head[N],val[N<<1];
int f[12][95][1<<12], f2[12][95][1<<12];
vector<int> v1[95],v2[95];
bool vis[1<<22];
ii read()
{
int x=0,f=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)
{
if(ch==‘-‘)
f=0;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return (f)?x:(-x);
}
iv add(int x,int y,int z)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
val[tot]=z;
}
int main()
{
n=read();
m=read();
d=read();
int a,b,c;
for(re i=1;i<=m;i++)
{
a=read();
b=read();
c=read();
add(a,b,c);
add(b,a,c);
}
int d1=(d>>1);
int d2=d-d1;
f[0][1][0]=1;
for(re i=0;i<d1;i++)
{
for(re j=1;j<=n;j++)
{
for(re k=head[j];k;k=next[k])
{
int p=to[k];
for(re s=0;s<(1<<i);s++)
{
f[i+1][p][s<<1|val[k]]|=f[i][j][s];
}
}
}
}
for(re i=1;i<=n;i++)
f2[0][i][0]=1;
for(re i=0;i<d2;i++)
{
for(re j=1;j<=n;j++)
{
for(re k=head[j];k;k=next[k])
{
int p=to[k];
for(re s=0;s<(1<<i);s++)
{
f2[i+1][p][s<<1|val[k]]|=f2[i][j][s];
}
}
}
}
for(re i=1;i<=n;i++)
{
for(re j = 0;j<(1 << d1);j++)
{
if(f[d1][i][j])
v1[i].push_back(j);
}
}
for(re i=1;i<=n;i++)
{
for(re j=0;j <(1<<d2);j++)
{
if(f2[d2][i][j])
v2[i].push_back(j);
}
}
for(re k=1;k<=n;k++)
{
for(re i=0;i<v1[k].size();i++)
{
for(re j=0;j<v2[k].size();j++)
{
if(vis[v1[k][i]<<(d2)|v2[k][j]])
continue;
vis[v1[k][i]<<(d2)|v2[k][j]]=1;
++ans;
}
}
}
printf("%lld\n",ans);
return 0;
}
T3 z
留坑