凡科免费建微信小程序网站,佛山网站建设招标,wordpress首页不显示最新文章,如何做响应式网站希望
题意#xff1a;
有A#xff0c;B两棵树#xff0c;对于一个1到n的全排列a[i],让树A中的点i和树B的节点a[i]连一条边#xff0c;希望指数#xff1a;两棵树和新加入的边构成的图中#xff0c;环长为m的环的个数。数组a[]可以任意交换位置#xff0c;且任意#…希望
题意
有AB两棵树对于一个1到n的全排列a[i],让树A中的点i和树B的节点a[i]连一条边希望指数两棵树和新加入的边构成的图中环长为m的环的个数。数组a[]可以任意交换位置且任意随机不限次数的交换。计算出期望情况下两棵树的希望指数 n≤300,3≤m≤7
题解
期望概率 * 对应的权值 在本题中概率肯定是1n!\frac{1}{n!}n!1,因此需要求所有情况下环长为m的环的个数 我们开始找环的分布情况一定是左侧的点和右侧的点通过之间加的点形成环如图图中环长为6 且所有环用到中间新建边只能为两条边可能会疑惑为什么像图中情况用到的新建边的数量为4不是2但是图中环的长度为8(这已经是新建边4所对应的环最小长度)而题目保证所求环长7,刚好不行。也就是其实题目是隐含着新建边最多用两条不可能更多 我们确定了中间边只能用2那就好说了比如让你求环为x的数量x先减2yx-2然后就是两个树一共构成长度为y因此我们预先处理出两个子树分别能组成长度为len的边的数量用桶来存。比如tong1[i]:表示在树A中长度为i的边的数量。那么答案就:tong1[i]∗tong2[m−i−2]∗2.0∗((n−2))tong1[i]*tong2[m-i-2]*2.0*((n-2))tong1[i]∗tong2[m−i−2]∗2.0∗((n−2)) i是树A需要提供的边m-i-2是树B需要提供的边乘2.0是因为边可以交叉和不交叉来正好两种而最后(n-2)!是什么我们之前说过最多用新增边为2那么说明左右各有两个点要被占用(因为一个边有两个点)而其他的点可以任意排列剩下的点就是(n-2)个任意排列就是阶乘 再讲一些细节 比如树上所有路径长度可以用floyd来求因为答案要乘(n-2)!而最终答案还要除以n!,所以直接除以n*(n-1)即可
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn400;
vectorinta[maxn],b[maxn],g[maxn];
int L[maxn];
int x[maxn][maxn];
int y[maxn][maxn];
int tong1[maxn],tong2[maxn];
int main()
{//rd_test();int n,m;cinnm;for(int i1;in;i){for(int j1;jn;j){x[i][j]1e9;y[i][j]1e9;}}for(int i1;in;i){int u,v;read(u,v);x[u][v]x[v][u]1;}for(int i1;in;i){int u,v;read(u,v);y[u][v]y[v][u]1;}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){x[i][j]min(x[i][j],x[i][k]x[k][j]);y[i][j]min(y[i][j],y[i][k]y[k][j]);}}}for(int i1;in;i){for(int ji1;jn;j){if(ij)continue;if(x[i][j]1e9)continue;if(y[i][j]1e9)continue;tong1[x[i][j]];tong2[y[i][j]];}}double ans0;for(int i1;im-3;i){ansans1.0*tong1[i]*tong2[m-i-2]*2.0/(1.0*n*(n-1));}printf(%.4lf\n,ans);//Time_test();
}
