AT5633 Counting of Trees

题目描述

见题目翻译

思路

https://oi-wiki.org/math/quick-pow/

首先，先要判定不合法的情况，即：

• 第一个数字一定为 $0$；
• 其余的数字一定不为 $0$。

遇到这个情况，用一个变量标记下来，输出 $0$

给出的样例无解就没有输出，但是实测会 WA ，必须输出 $0$ !!!

如果有解，那么很显然，即为每一层的结点的排列的乘积。

用桶或 map 记录每一层的结点，别忘了用快速幂优化。。。

三年 OI 一场空，不开 long long 见祖宗！！！

代码

#include <bits/stdc++.h>
using namespace std;

const int Mod = 998244353;

int N , T , MAXN , Ans = 1;

bool Flag = 1;

map<long long , long long> Tong;

long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

int main() {
	ios::sync_with_stdio(false);
	
	cin >> N;
	
	for(long long i = 0; i < N; i++) {
		cin >> T;
		Tong[T]++;
		MAXN = max(MAXN , T);
		if((i == 0 && T != 0) || (i != 0 && T == 0)) Flag = 0;
	}
	
	if(Flag) {
		for(long long i = 1; i <= MAXN; i++) {
			Ans = (Ans % Mod * binpow(Tong[i - 1] , Tong[i] , Mod) % Mod) % Mod;
		}	
		cout << Ans % Mod << endl;
	}	
	
	else cout << 0 << endl;
	
	return 0;
}