锐客网

  1. 首页 > it技术 > >

数学|【SRM 565 UnknownTree】计数 分类讨论

枚举数学Topcoder组合计数

【数学|【SRM 565 UnknownTree】计数 分类讨论】一个有N + 3个点的树，告诉你123号点到其他点的距离，求合法的边权为正整数的树个数。

#include #include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) #define Dwn(i, x, y) for (int i = x; i >= y; i --) #define RepE(i, x) for(int i = pos[x]; i; i = g[i].nex) using namespace std; typedef long long LL; typedef double DB; const int mod = 1000000009, N = 60; LL ans; int n, a[N], b[N], c[N], par[N], p0[N]; class UnknownTree { public: void Calc(int *a, int *b, int *c, int Dab, int Dac) { if (!Dab || !Dac) return ; a[n] = b[n + 1] = c[n + 2] = 0; a[n + 1] = b[n] = Dab, a[n + 2] = c[n] = Dac, b[n + 2] = c[n + 1] = Dab + Dac; LL sum = 1; memset(par, 0, sizeof(par)); Rep(j, 0, n - 1) { Rep(k, 0, n + 2) if (a[j] > a[k] && a[j] - a[k] == b[j] - b[k] && a[j] - a[k] == c[j] - c[k]) par[j] ++; if (par[j]) { (sum *= par[j]) %= mod; continue ; } Rep(k, 0, n + 2) if (j != k && a[j] == a[k] && b[j] == b[k] && c[j] == c[k]) sum = 0; if (a[j] + b[j] == Dab && c[j] - a[j] == Dac) continue ; if (a[j] + c[j] == Dac && b[j] - a[j] == Dab) continue ; sum = 0; } (ans += sum) %= mod; } void Work(int *a, int *b, int *c) { if (a[0] > b[0]) { if (a[0] < c[0]) Calc(a, b, c, a[0] - b[0], c[0] - a[0]); } else { if (a[0] > c[0]) Calc(a, b, c, b[0] - a[0], a[0] - c[0]); else Calc(a, b, c, b[0] - a[0], c[0] - a[0]); Calc(a, b, c, b[0] - a[0], a[0] + c[0]); } if (c[0] > a[0]) Calc(a, b, c, a[0] + b[0], c[0] - a[0]); } int getCount(vector A, vector B, vector C) { n = A.size(); Rep(i, 0, n - 1) a[i] = A[i], b[i] = B[i], c[i] = C[i]; Rep(i, 0, n - 1) { int Dab, Dac, Dbc; a[n + 1] = b[n] = Dab = a[i] + b[i]; a[n + 2] = c[n] = Dac = a[i] + c[i]; b[n + 2] = c[n + 1] = Dbc = b[i] + c[i]; memset(par, 0, sizeof(par)); LL sum = 1; bool fl = 0; Rep(j, 0, n - 1) if (j != i) { Rep(k, 0, n + 2) if (a[j] > a[k] && a[j] - a[k] == b[j] - b[k] && a[j] - a[k] == c[j] - c[k]) par[j] ++; if (par[j]) { (sum *= par[j]) %= mod; continue ; } Rep(k, 0, n + 2) if (j != k && a[j] == a[k] && b[j] == b[k] && c[j] == c[k]) fl = 1; if (a[j] < a[i] && (a[j] + b[j] != Dab || a[j] + c[j] != Dac)) fl = 1; if (b[j] < b[i] && (a[j] + b[j] != Dab || c[j] + b[j] != Dbc)) fl = 1; if (c[j] < c[i] && (a[j] + c[j] != Dac || c[j] + b[j] != Dbc)) fl = 1; if (a[j] >= a[i] && b[j] >= b[i] && c[j] >= c[i]) fl = 1; } if (!fl) (ans += sum) %= mod; } Rep(j, 0, n - 1) { Rep(k, 0, n - 1) if (a[j] > a[k] && a[j] - a[k] == b[j] - b[k] && a[j] - a[k] == c[j] - c[k]) p0[j] ++; if (!p0[j]) { swap(a[j], a[0]), swap(b[j], b[0]), swap(c[j], c[0]); break ; } } Work(a, b, c); Work(b, a, c); Work(c, a, b); return (int)ans; } };



    推荐阅读


    上一篇：C++|最大公约数&最小公倍数(GCD,LCM)

    下一篇：【hdu5304】生成树计数—基尔霍夫矩阵 DP