链接：https://www.nowcoder.com/acm/contest/144/C
来源：牛客网
The input starts with one line containing exactly one integer T which is the number of test cases. (1 ≤ T ≤ 20)18
Each test case contains one line with two integers N and M indicating the number of sets and the range of integers. (1 ≤ N ≤ 10
, 1 ≤ M ≤ 1018
,
)
For each test case, output "Case #x: y" in one line (without quotes), where x is the test case number (starting from 1) and y is the number of different results modulo 998244353.
Case #1: 4 Case #2: 52
题意 ： 给你N个空的集合，并且是满足集合的性质的，每次操作是将 i - N 变成一个随机的数，求最终的集合中会有多少种情况？
思路分析 ： 我们考虑这个问题，由于n, m 都非常大，因此我们考虑这个问题的时候可以这样去想，考虑一系列的操作后会有多少种颜色，假设会有K种颜色，那么方案数为 C(m, k)，将这几种颜色插入到集合中即可，由于集合具有互异性，因此集合内的元素只取决于某个数字首次出现的何处，注意 ， 第一个地方一定要有元素，因此是 K ， 剩下的 k-1 个元素插在 n-1 个余下的位置上，再全排列即可
代码示例 ：
using namespace std;
#define ll long long
const ll maxn = 1e6+5;
const ll mod = 998244353;
ll n, m;
ll qw(ll x, ll cnt){
ll res = 1;
while(cnt){
if(cnt&1) res *= x;
res %= mod;
x *= x;
x %= mod;
cnt >>= 1;
}
return res;
}
ll inv[maxn];
void init() {
for(ll i = 1; i <= 1000000; i++){
inv[i] = qw(i, mod-2);
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
ll t;
ll kas = 1;
init();
cin >> t;
while(t--){
cin >> n >> m;
ll num = min(n, m);
ll ans = m%mod;
ll sum = m%mod;
n %= mod, m %= mod;
for(ll i = 2; i <= num; i++){
sum = sum*(m-i+1+mod)%mod*(n-i+1+mod)%mod*inv[i-1]%mod;
ans = (ans+sum)%mod;
}
printf("Case #%lld: %lld\n",kas++, ans);
}
return 0;
}
原文：https://www.cnblogs.com/ccut-ry/p/9480503.html