LOJ #3119「CTS2019 | CTSC2019」随机立方体 (容斥)
2024-09-05 04:48:20
博客链接
里面有个下降幂应该是上升幂
还有个bk的式子省略了k^3
CODE
蛮短的
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000005;
const int mod = 998244353;
int fac[MAXN], inv[MAXN];
inline void PreWork(int N) {
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for(int i = 2; i <= N; ++i) {
fac[i] = 1ll * fac[i-1] * i % mod;
inv[i] = 1ll * (mod - mod/i) * inv[mod%i] % mod;
}
for(int i = 2; i <= N; ++i)
inv[i] = 1ll * inv[i-1] * inv[i] % mod;
}
inline int mul(int a, int b, int c) { return 1ll * a * b % mod * c % mod; }
inline int qpow(int a, int b) {
int re = 1;
while(b) {
if(b&1) re = 1ll * re * a % mod;
a = 1ll * a * a % mod; b >>= 1;
}
return re;
}
inline int C(int n, int m) { return n < m ? 0 : mul(fac[n], inv[m], inv[n-m]); }
int T, n, m, l, k, lim;
int a[MAXN], pre[MAXN], f[MAXN];
int main () {
PreWork(MAXN-5);
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d", &n, &m, &l, &k); lim = min(min(n,m),l);
if(k > lim) { puts("0"); continue; }
pre[0] = 1;
for(int i = 1; i <= lim; ++i) {
a[i] = (mul(n, m, l) - mul(n-i, m-i, l-i)) % mod;
pre[i] = 1ll * pre[i-1] * a[i] % mod;
}
pre[lim] = qpow(pre[lim], mod-2);
for(int i = lim-1; i >= 1; --i)
pre[i] = 1ll * pre[i+1] * a[i+1] % mod;
for(int i = 1; i <= lim; ++i)
f[i] = 1ll * mul(fac[n], fac[m], fac[l])
* mul(inv[n-i], inv[m-i], inv[l-i]) % mod
* pre[i] % mod;
int ans = 0; int sgn = 1;
for(int i = k; i <= lim; sgn=-sgn, ++i)
ans = (ans + 1ll * sgn * C(i, k) * f[i] % mod) % mod;
printf("%d\n", (ans + mod) % mod);
}
}
最新文章
- c++实现简单的链表
- Java学习笔记(二)&mdash;&mdash;变量与常量
- Python 练习 21
- 【LeetCode OJ】Valid Palindrome
- IOS异步和多线程操作&;&;在sqlite3中的应用
- javascript中onclick事件能调用多个方法吗
- Duilib介绍以及各个类的简介
- XML在JAVA项目中的作用
- avd name对AVD的创建的影响
- pack布局
- JAVA中的break[标签]continue[标签]用法
- ios简单实现如果没有开启定位,提示开启系统软件定位功能
- (五)Lua脚本语言入门
- Laravel使用Seeder自动填充数据
- This Handler class should be static or leaks might occur(null) 解决办法 (转)
- Linux:Day8(下) RAID
- opencv 进行图像的花屏检测(模糊检测)
- jQuery之$.ajax()方法详解及实例
- 了解一下 Linux 上用于的 SSH 图形界面工具
- hmac md5