题目链接:uva 1436 - Counting heaps
题目大意:给出一个树的形状,现在为这棵树标号,保证根节点的标号值比子节点的标号值大,问有多少种标号树。
解题思路:和村名排队的思路是一只的uva11174,最后问题只和树德结构有直接关系,f(root)=(s(root)−1)!(s(1)∗s(2)∗⋯∗s(n)
但是给定的取模数不是质数,所以不能用逆元做,只能将分子分母分别拆分成质因子,然后对质因子进制约分。因为最后的答案一定是正整数,所以对于每个质因子,分子分解出的因子个数一定大于等于分母分解出的,最后约分肯定剩下的是分子,再用快速幂求解。
剪枝,因为分解质因子的次数非常多,所以需要对分解函数剪枝,当u是质数时,可以直接终止返回。
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 500005;
typedef long long ll;
int P = 0, prime[N], ispri[N];
int n, f[N], vis[N], cnt[N];
ll mod;
void getPrime (int N) {
memset(ispri, 0, sizeof(ispri));
for (int i = 2; i < N; i++) {
if (ispri[i])
continue;
prime[P++] = i;
for (int j = 2 * i; j < N; j += i)
ispri[j] = 1;
}
}
void getNode () {
memset(cnt, 0, sizeof(cnt));
queue<int> que;
for (int i = 1; i <= n; i++)
if (vis[i] == 0)
que.push(i);
while (!que.empty()) {
int u = que.front();
que.pop();
cnt[u]++;
int v = f[u];
cnt[v] += cnt[u];
vis[v]--;
if (vis[v] == 0)
que.push(v);
}
}
void init () {
memset(vis, 0, sizeof(vis));
scanf("%d%lld", &n, &mod);
f[1] = 0;
for (int i = 2; i <= n; i++) {
scanf("%d", &f[i]);
vis[f[i]]++;
}
getNode();
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++)
vis[cnt[i]]++;
}
ll power (ll x, ll m) {
ll ans = 1;
while (m) {
if (m&1)
ans = ans * x % mod;
x = x * x % mod;
m /= 2;
}
return ans;
}
void cal (int u, int v) {
for (int i = 0; i < P; i++) {
int k = prime[i];
while (u % k == 0) {
cnt[k] += v;
u /= k;
}
if (ispri[u] == 0) {
cnt[u] += v;
return;
}
}
}
ll solve () {
memset(cnt, 0, sizeof(cnt));
for (int i = 2; i <= n; i++)
cal(i, 1);
for (int i = 2; i <= n; i++)
if (vis[i])
cal(i, -vis[i]);
ll ans = 1;
for (int i = 0; i < P; i++) {
ll u = prime[i];
if (cnt[u])
ans = (ans * power(u, cnt[u])) % mod;
}
return ans;
}
int main () {
getPrime(N);
int cas;
scanf("%d", &cas);
while (cas--) {
init();
printf("%lld\n", solve());
}
return 0;
}
分享到:
相关推荐
利用差分盒计数法计算图像分维数,利用matlab语言编写
hutc-Counting 代码参考hutc-Counting 代码参考hutc-Counting 代码参考
A possible characterisation of a fractal set is provided by the "box-counting" method: The number N of boxes of size R needed to cover a fractal set follows a power-law, N = N0 * R^(-DF), with DF<...
switch cnn官方开源文件,可能缺少训练集shanghaiTest,需要自己去下载
计算1D 2D 3D的分形盒维数。 分形维数被誉为大自然的几何学的分形(Fractal)理论,是现代数学的一个新分支,但其本质却是一种新的世界观和方法论
BOXCOUNT 对 D 维数组(其中 D=1,2,3)进行 Box-Counting。 Box-counting 方法可用于确定一个的分形属性1D 片段、2D 图像或 3D 阵列。 如果 C 是一个分形集,分形维数 DF < D,那么覆盖该集所需的大小为 R 的框...
基于vb的JCS---A计数天平数据采集
Bayesian-Crowd-Counting(ICCV 2019 口头报告) | ICCV 2019 口头论文“Bayesian Loss for Crowd Count Estimation with Point Supervision”的官方实现 可视化 贝叶斯 贝叶斯+ 密度 引文 如果您使用此代码进行...
Tensorflow 2对象计数 使用Tensorflow 2和Tensorflow Lite进行累计对象计数。 安装 克隆仓库git clone https://github.com/TannerGilbert/Tensorflow-2-Object-Counting 安装依赖 cd Tensorflow-2-Object-Counting ...
RGBD人群计数 PyTorch对CVPR2019论文的实施: “用于RGB-D人群计数和定位的密度图回归引导检测网络” [ ] [] 李东泽*,李静*,贾正,罗维新,高胜华 (*平等贡献) 要求 的Python:3.x 火炬:1.1+ 毫米波检测:...
ASTM D1423-16(2022)Twist in Yarns by Direct-Counting.pdf
ECCV2020:具有本地计数图的人群混合自适应回归网络 介绍 在这项工作中,我们介绍了一个称为局部计数图的新学习目标,并显示了其在局部计数回归中的可行性和优势。 同时,我们提出了一种从粗到精的方式的自适应混合...
使用 Box-Count 或 Box-Counting Dimension 的 FD 计算为: D = log (Nr)/log(r) 在哪里: D = 分形维数 Nr = 边长为 r 的盒子数 r = 盒子的比例 对于许多对象,分形盒计数维度可以通过 log(N) 与 log(1 ∕ s)...
MATLAB图像处理,使用界面设计GUI,对一幅图像中的红细胞进行计数
本手册为TI毫米波雷达应用手册,用于人员计数开发的开发指导,从程序场景设置到应用,介绍详细!
matlab code for box counting dimension
We report a frequency-multiplexing method for multi-beam photon-counting light detection and ranging (LiDAR), where only one single-pixel single-photon detector is employed to simultaneously detect ...
pipe-counting丝材计数管理软件
检测视频中出现的人头数目,并统计来往的人数。
点云算法调参文档