LGJOJ 存放处
一直找不到原题。。。
树与连通块
有一棵树，n个结点，结点编号1至n，有n-1条边，第i条边连接的结点是u[i]和v[i]。
如果某个图满足如下的所有条件，那么这个图就是树的子图：
1、子图的所有结点都来自于树的结点，即子图的结点是树的结点的子集。
2、不妨假设子图的结点所形成的集合是S。
3、子图的边来自于树的边；对于树的每一条边，如果这条边连接的两个结点都是集合S的点，那么这条边就属于子图的边，否则这条边
不属于子图的边。
所有某个子图恰好含有i个连通块，那么这个子图就是"i子图"
你要回答n个问题，第i个问题是： 有多少个不同的"i子图"？答案模998244353。其中1<=i<=n。
输入格式 第一行，一个整数n。 1 <= n <= 5000。
接下来有n-1行，每行描述一条边，第i行是u[i]和v[i]。
输出格式 共n行，每行一个整数。
输入/输出例子1 输入：
4
1 2
2 3
3 4
输出：
10
5
0
0
输入/输出例子2 输入：
2
1 2
输出：
3
0
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353, N = 5005;
int n, siz[N];
long long f[N][N][2], tmp[N][2];
vector<int> g[N];
void dfs(int u, int father) {
f[u][1][1] = 1;
f[u][0][0] = 1;
siz[u] = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == father) continue;
dfs(v, u);
for (int k = 0; k <= siz[u]; k++) tmp[k][0] = f[u][k][0], tmp[k][1] = f[u][k][1];
for (int j = 0; j <= siz[u]; j++) {
for (int k = 0; k <= siz[v]; k++) {
if (j+k-1>=0) f[u][j+k-1][1] = (f[u][j+k-1][1]+tmp[j][1]*f[v][k][1])%MOD;
if(k!=0)f[u][j+k][1] = (f[u][j+k][1]+tmp[j][1]*f[v][k][0])%MOD;
f[u][j+k][0] = (f[u][j+k][0]+tmp[j][0]*f[v][k][1])%MOD;
if (k != 0) f[u][j+k][0] = (f[u][j+k][0]+tmp[j][0]*f[v][k][0])%MOD;
}
}
siz[u] += siz[v];
}
}
int main()
{
cin >> n;
for (int i = 0, u, v; i < n-1; i++) {
cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
dfs(1, -1);
for (int i = 1; i <= n; i++) {
cout << (f[1][i][0]+f[1][i][1])%MOD << endl;
}
return 0;
}卡片
有n种类型的卡片，第i种类型的卡片的初始价值是a[i]元/张，第i种类型的卡片的限额是b[i]张。
额度的意思是你最多可以购买多少张这种类型的卡片。
有Q个操作，每个操作是如下的3种格式之一：
一、 格式为 1 x y, 表示把第x种类型的卡片的价值修改为y元/张。 1<=x<=n, 0 <= y <= 1e9。
二、 格式为 2 x y, 表示把第x种类型的额度修改为y。1<=x<=n, 0 <= y <= 1e9。
三、 格式为 3 x, 我们称这种操作是“查询”，表示假如你需要购买x张卡片，但每种卡片都不能超额度购买，
应该如何购买，使得购买到的x张卡片的总价值最大，输出最大总价值，如果无法购买满足条件，输出-1。 1<=x<=1e9。
注意：每个操作都是独立的，“查询”操作不是真的购买，只是为了让你回答问题而已。
输入格式 第一行，一个整数n， 1 <= n <= 2e5。
接下来有n行，第i行是a[i]和b[i]，0<=a[i]<=1e9, 0<=b[i]<=1e4。
接下来一行是一个整数Q, 1<=Q<=2e5。
接下来是Q行，每行一个操作，每个操作是题目所述的3种操作之一。
输出格式 对于每一个“查询”操作，都输出一个整数，然后换行。
输入/输出例子1 输入：
3
1 1
2 2
3 3
7
3 4
1 1 10
3 4
2 1 0
2 3 0
3 4
3 2
输出：
11
19
-1
4
样例解释 对于第一个“查询”操作，购买1张第2种类型的卡片，再购买3张第3种类型的卡片，总价值是2+3*3=11。
对于第二个“查询”操作，购买1张第1种类型的卡片，再购买3张第3种类型的卡片，总价值是10+3*3=19
#include <bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, a[N], b[N];
struct node {
long long sum, num;
} t[10*N];
int ls[10*N], rs[10*N];
int root = 0, cnt = 0;
void pushup(int r) {
t[r].sum=t[ls[r]].sum+t[rs[r]].sum;
t[r].num=t[ls[r]].num+t[rs[r]].num;
}
void modify(int &u, int l, int r, int pos, int val) {
if (!u) {
u = ++cnt;
t[u].sum = t[u].num = 0;
}
if (l ==r) {
t[u].num += val;
t[u].sum += (long long)val*l;
return;
}
int m = (l+r)>>1;
if (pos > m) modify(rs[u], m+1, r, pos, val);
else modify(ls[u], l, m, pos, val);
pushup(u);
}
long long query(int u, int l, int r, int p) {
if (!u) return 0;
//cout << "[" << l << "," << r << "] " << p << endl;
int m = (l+r)>>1;
if (t[u].num == p) {
return t[u].sum;
}
if (t[rs[u]].num >= p) {
return query(rs[u], m+1, r, p);
} else if (l != r) {
return query(ls[u], l, m, p-t[rs[u]].num)+query(rs[u], m+1, r, t[rs[u]].num);
} else {
return (long long)l*min((long long)p, t[u].num);
}
}
int main()
{
t[0].sum = t[0].num = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i], &b[i]);
modify(root, 0, 1e9, a[i], b[i]);
}
int q;
scanf("%d", &q);
while (q--) {
int op, x, y;
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &x, &y);
modify(root, 0, 1e9, a[x], -b[x]);
a[x] = y;
modify(root, 0, 1e9, a[x], b[x]);
} else if (op == 2) {
scanf("%d%d", &x, &y);
modify(root, 0, 1e9, a[x], y-b[x]);
b[x] = y;
} else {
scanf("%d", &x);
if (t[root].num < x) printf("-1\n");
else printf("%lld\n", query(root, 0, 1e9, x));
}
}
return 0;
}网络（2023.5.29）
有一个h行w列的网格，每个格子一开始都有一个数字0，有两种操作：
1、行操作，选中一行，0变1，1变0。
2、列操作，选择一列，0变1，1变0。
总共要进行r次行操作和c次列操作，目标是最后网格有s个1，有多少种不同的方案？答案模555555555。
同一行可以进行多次重复“行操作”，同一列可以进行多次“列操作”。
两种方案不同是指：存在某行或者某列，在两种方案中，操作的次数不同。
输入格式 多组测试数据。
第一行，一个整数g，表示有g组测试数据，g<=5。
每组测试数据格式：一行，5个整数， h, w,r,c,s。 1<=h,w<=1555, 0<=r,c<=1555， 0<=s<=h*w。
输出格式 共g行，每行一个整数。
输入/输出例子1 输入：
4
2 2 2 2 4
2 2 0 0 1
10 20 50 40 200
1200 1000 800 600 4000
输出：
4
0
333759825
96859710
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 555555555;
ll C[3200][3200];
// 1 1200 1000 800 600 4000
int main()
{
C[0][0] = 1;
for (int i = 1; i < 3200; i++) {
C[i][0] = 1;
for (int j = 1; j < 3200; j++) {
C[i][j] = C[i-1][j-1]+C[i-1][j];
C[i][j] %= MOD;
}
}
int g;
cin >> g;
while (g--) {
ll h, w, r, c, s;
cin >> h >> w >> r >> c >> s;
ll ans = 0;
for (ll i = r%2; i <= min(h, r); i+=2) { // 实际变 i 行
for (ll j = c%2; j <= min(w, c); j+=2) { // 实际变 j 列
ll ts = i*w+j*(h-i)-i*j;
if (ts != s) continue;
ll ti = C[(r-i)/2+h-1][h-1], tj = C[(c-j)/2+w-1][w-1];
ans += (((C[h][i]*C[w][j])%MOD*ti)%MOD*tj)%MOD;
ans %= MOD;
}
}
cout << ans << endl;
}
return 0;
}边的方向（2023.07.02）
有一个无向图,它有n个节点，有m条边，其中节点编号1至n，边的编号1至m。
第i条无向边连接u[i]和v[i]节点，数据保证没有重边，也没自环。
现在要对每一条无向边定方向，即变成有向图。
若没有任何限制，那么显然共有2^m种不同的方案，但是我们希望：
每个结点u，它的出边有且只有1条，那么有多少种不同的合法的方案？
答案模998244353。
输入格式 第一行，两个整数，n和m， 其中2<=n<=2e5， 1<=m<=2e5。
接下来有m行，第i行是u[i]和v[i]。1<=u[i],v[i]<=n。
输出格式 一个整数。
输入/输出例子1 输入：
3 3
1 2
1 3
2 3
输出：
2
输入/输出例子2 输入：
2 1
1 2
输出：
0
输入/输出例子3 输入：
7 7
1 2
2 3
3 4
4 2
5 6
6 7
7 5
输出：
4
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
#define ll long long
const ll MOD = 998244353;
vector<int> g[N];
int n, m;
int u[N], v[N], cnt[N];
int fa[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
fa[u] = v;
}
ll po(ll x, ll n) {
ll t = 1;
while (n) {
if (n%2) t = t*x%MOD;
x = x*x%MOD;
n >>= 1;
}
return t;
}
bool del[N];
bool flag = 0;
void delet(int u) {
del[u] = 1;
cnt[u]--;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (del[v]) continue;
cnt[v]--;
if (cnt[v] == 1) delet(v);
}
}
bool chk(int u) {
if (cnt[u] != 2) return 0;
del[u] = 1;
int ret = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (del[v]) continue;
ret &= chk(v);
}
return ret;
}
int main()
{
cin >> n >> m;
if (m < n) {
cout << 0 << endl;
return 0;
}
for (int i =1; i <= n; i++) fa[i] = i;
for (int i= 0; i <m; i++) {
cin >> u[i] >>v[i];
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
merge(u[i], v[i]);
cnt[u[i]]++;
cnt[v[i]]++;
}
for (int i = 1; i <= n; i++) {
if (g[i].size() == 0) {
cout << 0 <<endl;
return 0;
}
if (g[i].size() == 1) delet(i);
}
ll ans = 1;
for (int i = 1; i <= n; i++) {
if (del[i]) continue;
if (!chk(i)) {
cout << 0 << endl;
return 0;
}
ans *= 2;
ans %= MOD;
}
cout << ans << endl;
return 0;
} 游戏得分（2023.07.02）
设P是1至n的某个排列。有n个玩家参加游戏，编号1至n，还有一个裁判。
一开始，第i个小球在第i个玩家手上。
每次当裁判一吹哨，第i个玩家就会把他手上的球交给第P[i]个人，这n个人是同步进行的，
若i等于P[i]，那么该玩家的球就相当于不用动。
裁判至少会吹第一次哨，那么游戏什么时候停止呢？
若对于所有的1<=i<=n都满足第i个球就在第i个人手上，那么游戏就会停止，
否则裁判就会再次吹哨，游戏继续，数据保证，游戏一定能停止。
对于某个特定的排列P，假设游戏结束时，裁判吹哨的次数为x，那么该排列的得分，其中k是读入的 。
因为P是1至n的某个排列，然而1至n的排列总共有n!个不同的排列，我们需要求出这n!个排列的总得分。
答案模998244353。
输入格式 第一行，两个整数，n和k。2<=n<=50, 1<=k<=10000。
输出格式 一个整数。
输入/输出例子1 输入：
2 2
输出：
5
输入/输出例子2 输入：
3 3
输出：
79
输入/输出例子3 输入：
50 10000
输出：
77436607
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 90;
const ll MOD = 998244353;
ll n, k;
ll po(ll x, ll n) {
ll t = 1;
while (n) {
if (n%2) t = t*x%MOD;
x = x*x%MOD;
n >>= 1;
}
return t;
}
ll fa[N], inv[N], invf[N];
ll f[N][N];
ll C(ll n, ll m) {
return fa[n]*invf[n-m]%MOD*invf[m]%MOD;
}
ll ans = 0;
ll cur[N];
void dfs(int len, int sum) {
if (sum == n) {
ll cnt = 1;
ll ts = 0, lcm = 1;
for (int i = 1; i < len; i++) {
ll j = i;
cnt = cnt*C(n-ts, cur[i])%MOD;
cnt = cnt*fa[cur[i]-1]%MOD;
ts += cur[i];
while (j+1 < len && cur[j+1] == cur[i]) {
j++;
cnt = cnt*C(n-ts, cur[i])%MOD;
cnt = cnt*fa[cur[i]-1]%MOD;
ts += cur[i];
}
cnt = cnt*invf[j-i+1]%MOD;
lcm = lcm*cur[i]/__gcd(lcm, cur[i]);
i = j;
}
ans = (ans+cnt*po(lcm, k)%MOD)%MOD;
return;
}
for (int i = max(1ll, cur[len-1]); sum+i <= n; i++) {
cur[len] = i;
dfs(len+1, sum+i);
}
}
int main()
{
inv[1] = inv[0] = invf[0] = invf[1] = fa[1] = fa[0] = 1;
for (int i = 2; i <= 80; i++) {
fa[i] = fa[i-1]*i%MOD;
inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;
invf[i] = invf[i-1]*inv[i]%MOD;
}
cin >> n>> k;
dfs(1, 0);
cout <<ans << endl;
return 0;
}