【数学】JZOJ_4786 小a的强迫症

本文主要是介绍【数学】JZOJ_4786 小a的强迫症，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出$n$种颜色的球以及它们的个数，把它们排成一排，排列中第$i$种颜色的珠子一定要排在第$i+1$种颜色的最后一个珠子颜色之前，求出排列总数。

思路

按珠子的颜色分别处理。
当前珠子有$x$个，那么除了最后一个，其他的珠子都可以在前面$sum-1$个位置中随便排。

代码

#include<cstdio>
#include<algorithm>
#define M 998244353long long f[500001], ans=1; 
int n, x, sum;int power(int a, int b) {int res = 1;for (; b; b >>= 1) {if (b & 1) res = (long long)res * a % M;a = (long long)a * a % M;}return res;
}int C(int n, int m) {return f[n] * power(f[n - m], M - 2) % M * power(f[m], M - 2) % M;
}int main() {scanf("%d", &n);f[0] = 1;for (int i = 1; i <= 500000; i++)f[i] = f[i - 1] * i % 998244353;for (int i = 1; i <= n; i++){scanf("%d", &x);sum += x;ans = ans * C(sum - 1, x - 1) % M;}printf("%lld\n", ans);
}

这篇关于【数学】JZOJ_4786 小a的强迫症的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---