当前位置: 首页 > news >正文

Luogu P11159 【MX-X6-T5】 再生 题解 [ 蓝 ] [ 前缀和 ] [ 组合计数 ]

再生

笑点解析:一开始乘法原理推错式子胡了个依赖链长种类数 \(\le \sqrt n\) 的做法上去。

有了 \(top\) 数组,显然可以求出每个点所处的长链。对于长链上的点,如果链长为 \(x\),那么这条链有 \((x - 1)!\) 种可能的情况,因为链头是已经被确定了的

考虑对形态计数。显然大的长链不能接到短的长链上。于是将链长从大到小排序,如果把长为 \(x\) 的链接到长度为 \(y\) 的链上,则有 \(y - x\) 种情况。对于当前添加的链,显然可以把这些情况直接相加,维护一个 \(\sum y - x\) 的式子,最后乘到总方案数里即可。

可以桶排序 + 前缀和维护,时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 500005;
const ll mod = 20051131;
int n, top[N], a[N];
ll ans = 1, f[N], tot[N];
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;f[0] = 1;for(int i = 1; i <= n; i++){cin >> top[i];a[top[i]]++;f[i] = (f[i - 1] * i) % mod;}for(int i = 1; i <= n; i++){if(a[i] == 0) continue;ans = (ans * f[a[i] - 1]) % mod;tot[a[i]]++;}ll suf = 0;for(int i = n, j = 0; i >= 1; i--){while(tot[i]--){if((suf - j * i) != 0) ans = (ans * (suf - j * i) % mod) % mod;suf += i;j++;}}cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=36179

相关文章:

  • 王浩宇 102500416
  • 程序员修炼之路:从小工到专家 读书笔记 2
  • 程序员修炼之路:从小工到专家 读书笔记 3
  • 中级问题
  • 2025.10.21
  • 解答在同步以太坊事件数据时,如何保证后端服务在 API/RPC 不稳定情况下的可用性
  • 程序员修炼之道:从小工到专家 读书笔记 1
  • 好想好想你
  • 10.21日学习笔记
  • 数据库概述
  • 第1天(简单题 基础语法 数据类型、条件判断 、循环 循环嵌套、位运算, ASCII 码)
  • 24信计2班 17曾向嵩 pytorch读书报告
  • 关于第一次作业的时长统计
  • Go 语言问题解释
  • Keil_v5的用法
  • day 8
  • OI 笑传 #21
  • Day1文本格式化标签
  • 【C语言学习记录】你好世界
  • 1021
  • 24信计2班 17曾向嵩 pytorch66页实验题
  • 解答这些常见的智能合约安全问题,并提供相应的防护措施
  • Day1排版标签,标题与段落
  • 读AI赋能05消费者盈余
  • 解答这些 Solidity 开发中的重要问题
  • grpc 哼哈二将,你值得拥有
  • 解释这些 Solidity 智能合约的核心概念
  • C++编程练习
  • 数据结构练习
  • newDay14