前沿
预计得分 (30 + 100 + 0)
实际得分 (30 + 80 + 0)
原因：我觉得是机房机子慢，放洛谷上不到 (1s) 就过了，在机房时限 (2s) 都过不去(哈哈，主要是把 (std) 给 (gan) 掉了)
T1 没有脑子的高精度
就真的，只为了考个高精度，绝了
给定 (n) 个数 (a_i) ，输出 (sum_{i=1}^{n}a_i!) (n,a_ileq 100)
【solution】:
我们直接预处理一下 (a_i!) 时间复杂度正确性显然，但是当 (a_i = 25) 左右的时候，你的 (long long) 就已经炸掉了，所以需要写高精度，不过谁能想到高精度竟然占到 (70) 分。
【Code】
无高精度的 (30) 代码
/*
By:Zmonarch
知识点 ：
竟然考高精度，没想到没想到，打个 30 跑
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int unsigned long long
#define qwq register
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 998244353 ;
inline int read() {
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ;}
while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ;}
return x * f ;
}
signed main(){
freopen("a.in" , "r" , stdin) ;
freopen("a.out" , "w" , stdout) ;
int n = read() , ret = 0 ;
for(qwq int i = 1 ; i <= n ; i++)
{
int x = read() , tmp = 1 ;
for(qwq int j = 1 ; j <= x ; j++) tmp *= j ;
ret += tmp ;
}
printf("%lld
" , ret) ;
return 0 ;
}
高精度 ： 这里给一下 (std) , 我抽空专门去搞一下高精度
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define fi first
#define se second
#define MP make_pair
int read()
{
int v = 0, f = 1;
char c = getchar();
while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
return v * f;
}
int n;
struct B
{
int a[500], len;
B()
{
for (int i = 0; i < 500; i++)
a[i] = 0;
len = 0;
}
} fac[200];
B operator + (const B &a, const B &b)
{
B c;
c.len = max(a.len, b.len);
for (int i = 0; i <= c.len; i++)
c.a[i] = a.a[i] + b.a[i];
for (int i = 0; i <= c.len; i++)
if (c.a[i] >= 10)
{
c.a[i + 1]++;
c.a[i] -= 10;
}
if (c.a[c.len + 1])
c.len++;
return c;
}
B operator * (const B &a, const int &b)
{
B c;
c.len = a.len;
for (int i = 0; i <= c.len; i++)
c.a[i] = a.a[i] * b;
for (int i = 0; i <= c.len + 10; i++)
{
c.a[i + 1] += c.a[i] / 10;
c.a[i] %= 10;
}
for (int i = c.len + 10; i >= 0; i--)
if (c.a[i])
{
c.len = i;
break;
}
return c;
}
int main()
{
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
n = read();
fac[0].a[0] = 1;
for (int i = 1; i <= 100; i++)
fac[i] = fac[i - 1] * i;
B ans;
while (n--)
ans = ans + fac[read()];
for (int i = ans.len; i >= 0; i--)
printf("%d", ans.a[i]);
puts("");
}
T2 容斥原理板子题
我和个 (der) 一样
给 (n imes m) 的矩形染色，每一个点都有 (k) 种颜色，求没有任意一
行或任意一列颜色相同的方案数。并对 (998244353) 取膜
【Solution】:
我们考虑当直接去求这个方案数，显然是不大可行的。所以我们考虑一下他的补集，最后减去就好了。
- 全集 ： (k^{n imes m}) ，也就是 (n imes m) 个点随便染色。
我们考虑删掉 (n) 行中有任意 (1) 行颜色相同的方案数。但是这个时候，我们删多了，所以我们需要将任意两行颜色相同的方案数加回来，我们在删或减得时候，不要考虑的太多，眼前事眼前做就好。
我们不难发现这个一个容斥原理，所以前面的系数这是显然的 (-1^k)
也就是当为奇数的时候，我们删，为偶数时候，加回来。
我们考虑当前行的时候 ：
我们就有这么个式子表示当前有 (i) 行的颜色是相同的方案数 ：
- 随机在 (n) 中选择 (i) 行 ( imes) 在这 (i) 行中有多少种颜色 ( imes) 剩下的矩阵随便排的方案数 。
- 表达式为 (C_{n}^{i} imes k^i imes k^{(n - i ) imes m})
我们考虑一下列时候
我们发现和行是一样的，你可以将矩形旋转 (90') 看和上述的玩意是一样的。无非是将上面的行换成了列而已吧
- 表达式 ： (C_{m}^{i} imes k^{i} imes k^{(m - i) imes n})
这个才是最难的。 既有行又有列的时候，
我们这波套式子 ：
- 文字表达式为 (k) 种颜色 $ imes $ 每一种颜色对应的方案数
即为 ：
[ksum_{i =1}^{n}sum_{j=1}^{m}C_{n}^{i}C_{m}^{j} k^{(n - i)(m - j)}
]
然后吧，这个题的 (n,mleq 10^6) 显然不可过，那么我们搞一下
[ksum_{i=1}^{n}C_{n}^{i}sum_{j=1}^{m}C_{m}^{j}k^{(n - i)(m - j)}
]
你的，把 (k^{n-i}) 当做一个整体 (w) ，然后，这是一个非常显然的二项式定理，就可过了
[ksum_{i=1}^{n}C_{n}^{i} imes ((k^{n - i} - 1)^{m} - k^{(n - i) imes m})
]
【Code】
/*
By:Zmonarch
知识点 ：
一开始以为是个简单的快速幂 + 组合数 ， 结果样例过不去，55 ，容斥原理、
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
#define qwq register
#define inl inline
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 998244353 ;
inline int read() {
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ;}
while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ;}
return x * f ;
}
int f[kmaxn] , Inv[kmaxn] ;
int n , m , k ;
void init() {
f[0] = 1 ; Inv[0] = Inv[1] = 1 ;
for(qwq int i = 1 ; i <= 1000000 ; i++) f[i] = f[i - 1] * i % kmod ;
for(qwq int i = 2 ; i <= 1000000 ; i++) Inv[i] = (- kmod / i + kmod) * Inv[kmod % i] % kmod ;
for(qwq int i = 1 ; i <= 1000000 ; i++) Inv[i] = Inv[i - 1] * Inv[i] % kmod ;
}
int quick(int a , int b) {
int ret = 1 ;
while(b)
{
if(b & 1) ret = ret * a % kmod ;
a = a * a % kmod ;
b >>= 1 ;
}
return ret ;
}
int C(int n , int m) {return f[n] * Inv[m] % kmod * Inv[n - m] % kmod ;}
signed main(){
freopen("b.in" , "r" , stdin) ;
freopen("b.out" , "w" , stdout) ;
init() ; n = read() , m = read() , k = read() ;
int ans = quick(k , n * m) ;
for(qwq int i = 1 ; i <= n ; i++) //同行的
{
// 容斥原理，前面的系数为（-1）^ i
if(i & 1) ans = (ans - C(n , i) * quick(k , i) % kmod * quick(k , (n - i) * m) % kmod + kmod) % kmod ;
else ans = (ans + C(n , i) * quick(k , i) % kmod * quick(k , (n - i) * m) % kmod + kmod) % kmod ;
}
for(qwq int i = 1 ; i <= m ; i++) //我判断一下同行的,将 m 和 n 换换
{
if(i & 1) ans = (ans - C(m , i) * quick(k , i) % kmod * quick(k , (m - i) * n) % kmod + kmod) % kmod ;
else ans = (ans + C(m , i) * quick(k , i) % kmod * quick(k , (m - i) * n) % kmod + kmod) % kmod ;
}
for(qwq int i = 1 ; i <= n ; i++) // 既有行又有列的情况
{
if(i & 1) ans = (ans - C(n , i) * k % kmod * ((quick(quick(k , n - i) - 1 , m ) - quick(k , (n - i) * m) + kmod )) % kmod + kmod) % kmod ;
else ans = (ans + C(n , i) * k % kmod * ((quick(quick(k , n - i) - 1 , m ) - quick(k , (n - i) * m) + kmod )) % kmod + kmod) % kmod ;
}
printf("%lld
" , ans) ;
return 0 ;
}
T3 看不懂的题目
你需要设计一套纸币系统，现在已经有了 (n) 种不同样式的纸币，
你只需要为它们设计面值。每种纸币的面值都是 (B) 的约数（不同种纸
币面值可以相同），但是 (B) 还未知，只知道 (L<=B<=R),在这个国家，
支付时会给定 (d)，只要支付的总额模 (K) 与 (d) 同余即可。为了让人们能
应对支付时给出不同 d 的所有情况（假设可以使用的纸币没有限制），
请问你在 (B) 取值的所有可能性下设计方案数的和。对 (998244353) 取膜
【solution】:
如题面 : 看不懂。
教训 ：
- 考试不要乱翻机子， 浪费时间
- 学会高精度，谁能想到高精度竟然占了 (70) 分。