首页 > 其他分享 >AtCoder Regular Contest 106 F Figures

AtCoder Regular Contest 106 F Figures

时间:2023-04-17 20:44:41浏览次数:53  
标签:AtCoder typedef limits sum long Regular Figures ll

洛谷传送门

AtCoder 传送门

晚自习的时候胡出来的做法(((

首先你会发现题目等价于求 \(\sum\limits_{(\sum\limits_{i=1}^n a_i) = 2(n-1) \land \forall i \in [1,n], 1 \le a_i \le d_i} \prod\limits_{i=1}^n \dfrac{d_i!}{(d_i - a_i)!}\)。翻译一下就是枚举每个点的度数 \(a_i\)(一个结论是当度数总和 \(= 2(n-1)\) 并且每个点的度数都为正整数时一定能构造出合法的树),然后乘上对应的有序选择点内的洞的方案。

你会发现如果固定 \(a_i\),这个东西的组合意义是把 \(\sum\limits_{i=1}^n d_i\) 个数分成 \(n\) 组每组 \(d_i\) 个数,再在每组有序选出 \(a_i\) 个数。\(a_i \ge 1\) 比较烦,不妨整体减 \(1\),也就是一开始每组先选一个数,这样就变成了 \(a_i \ge 0\)。然后就发现可以把组合并起来考虑,即答案为先在每组中选一个数再在 \(\sum\limits_{i=1}^n (d_i - 1)\) 个数内有序选择 \(\sum\limits_{i=1}^n (a_i - 1) = n - 2\) 个数的方案数,即 \((\prod\limits_{i=1}^n d_i) \dfrac{(\sum\limits_{i=1}^n (d_i - 1))!}{(n-2)!}\),这个东西可以 \(O(n)\) 计算。

code
// Problem: F - Figures
// Contest: AtCoder - AtCoder Regular Contest 106
// URL: https://atcoder.jp/contests/arc106/tasks/arc106_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;
const ll mod = 998244353;

ll n, a[maxn];

void solve() {
	scanf("%lld", &n);
	ll s = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		s += a[i];
	}
	if (s < (n - 1) * 2) {
		puts("0");
		return;
	}
	s -= n;
	ll ans = 1;
	for (int i = 1; i <= n; ++i) {
		ans = ans * a[i] % mod;
	}
	for (int i = 0; i < n - 2; ++i) {
		ans = ans * ((s - i) % mod) % mod;
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,limits,sum,long,Regular,Figures,ll
From: https://www.cnblogs.com/zltzlt-blog/p/17327433.html

相关文章

  • ABC297F AtCoder Beginner Contest 297 F - Minimum Bounding Box 2
    https://atcoder.jp/contests/abc297/tasks/abc297_f在\(n\timesm\)的棋盘上放置\(k\)个棋子,记矩形A为能覆盖所有\(k\)个棋子的最小的矩形,求A的面积的期望将问题反过来考虑,枚举每种矩形有多少种放置棋子的方案,对于一个\(n\timesm\)的矩形,我们可以用容斥的方法......
  • AtCoder Beginner Contest 295
    ThreeDaysAgo我们定义一个只由数字构成的字符串中的字符能够被重排成相同的两份,我们称这个字符串是个好字符串,比如12341234现在给定一个字符串\(S\),找出所有的\([l,r]\),使得在这段区间中的子段是个好字符串题解:思维+组合计数首先我们根据题意得到:一个好字符串中所有相......
  • Atcoder题解:Agc002_f
    我们可以把这个理解成一种类似卡塔兰数的形式,我们发现,被安排的\(0\)球总数\(i\)和已经出现的颜色种数\(j\)在任意时刻都必须满足\(i\gej\)。然后就可以\(dp\)了,我们每次钦定下一个转移的球是某种颜色。如果下一个转移的球不是\(0\),那么我们就一次性把后面所有这种颜色......
  • Atcoder题解:Agc004_e
    \[吓死我了,还以为写了半天的被自己删掉了\]\[但是\text{Ctrl+S}会保存草稿啊\]\[以后一定要保留这个好习惯\]第一步转化题意,我们把“所有机器人移动”转化成“出口带着边框移动”,而在出口运动过程中超出边框的机器人,就“死”了。然后我们发现,出口运动过程中,假设出口目前走到......
  • Atcoder题解:Agc013_e
    我们考虑转化题意,一个合法的将\(1\simN\)划分成长度依次为\(a_1,a_2,\cdotsa_k\)的小区间,对答案的贡献为\(a_1^2a_2^2\cdotsa_k^2\)。化贡献为方案数,我们在每个长度为\(a_i\)的小区间内放置两个独立的标记,每个合法的划分方案对放置标记方案种数的贡献恰好是其对最终答......
  • AtCoder 板刷 / vp 记录
    ARC104AtCoder传送门A题解一道小学数学题,$X=\frac{A+B}{2},Y=\frac{A-B}{2}$。B题解一道暴力题。发现子串合法的充要条件是$cnt_{\text{A}}=cnt_{\text{T}}\landcnt_{\text{G}}=cnt_{\text{C}}$,暴力统计即可。C题解简单区间dp。发现$[1,2n]$可以拆......
  • AtCoder Regular Contest 104 F Visibility Sequence
    洛谷传送门AtCoder传送门考虑连边\((i,p_i)\)(若\(p_i=-1\)则不连边),可以发现形成了一篇内向树森林且这个森林存在一个dfs序为\(1,2,...,n\)。这棵森林有如下性质:\(\forallv\inson_u,h_u>h_v\)\(\forallv,w\inson_u\landv<w,h_v\leh_w\)考虑一个\(p......
  • AtCoder Beginner Contest 223(D,E,F)
    AtCoderBeginnerContest223(D,E,F)D(拓扑排序)D大意就是有\(n\)个点,\(m\)个关系,其中关系是指\(u\)和\(v\),在排序里面使得\(u\)的位置再\(v\)的位置的前面要求找到一个排序满足上述条件的序列中字典序最小的那一个这个使用拓扑排序,并加上优先队列即可只要找到\(n\)个数,即为......
  • AtCoder Beginner Contest 293 补题记录 (E-G)
    E题意:给定A,X,M,计算(A0+A1+A2+...+AX-1)modM(1<=A,M<=109,1<=X<=1012)。 根据等比数列求和公式,(A0+A1+A2+...+AX-1)modM=((AX-1)/(A-1))modM。然而,此题如果用求和公式来求解显然是行不通的,下面会给出原因。 如果我们要用求......
  • AtCoder Regular Contest 104 D Multiset Mean
    洛谷传送门AtCoder传送门很平凡的一道计数啊。考虑将所有数都减去\(x\),那么就要求选的数和为\(0\)。正负分开考虑,\(0\)可以任意选。需要多重背包求\(f_{i,j}\)表示选\(1\simi\)的数和为\(j\)的方案数。前缀和优化是平凡的。code//Problem:D-MultisetMean......