NOI Online #2提高组

第二场CCF线上凉心赛

期望得分200,实际得分90?

为什么呢?一共两个锅:

T1 k = 1 要特判
T2 不defineintlonglong见祖宗

总结出的解决办法:

自己注意,注意不了你就命没
以后看上去要溢出的都define一下

所以我以后将变成define大怪

T1题解

考虑直接同时倍增,显然只有小数的颜色能够连续k个,设 $p_1<p_2$

然后我们就可以找到在 $%p_2$ 意义下 $p_1$ 的最小开头

然后如果那个开头再向后跳都跳不出k个就绝不无聊,否则可以无聊

然后你会发现如果k=1则一定无聊 $puts("No")$

发现很像hh的项链,直接考虑扫描线

从左到右扫,我们只考虑计算右端点在当前扫到的pos的所有区间询问的答案

然后我们可以用 $pre[a[i]]$ 记 $a[i]$ 最近出现位置,这样你会发现对于左端点在l的询问,他的答案就是 $sum[l,r]$

现在我们有 $n^2$ 组询问,所以要处理一个后缀和

考虑节点合并函数

维护一个len,sum,ans,suf表示这个点代表的长度,这个点内有多少1,后缀平方和,后缀和

然后sum,len的更新还用我说?

suf的更新考虑+ $len_{ls}*sum_{rs}$

ans的更新?相当于

\sum(suf[i]+sum_{rs})^2

=ans_{ls}+len_{ls}*sum_{rs}*sum_{rs}+2*suf_{ls}*sum_{rs}

最后别忘加上 $ans_{rs}$

这个确实挺难,首先补集转换一下,为什么呢?因为看上去我们能求的从不是子孙后代变为是子孙后代的了...能简单一些

然后二项式反演(这我能想的到啊(#`O′))

我们记"恰好k次非平局"方案数是g(k),"至少k次非平局方案数"是f(k)

f(n)=\sum_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum_{i=n}^m(-1)^{i-n}{i\choose n}f(i)

所以我们要求答案g(k)只需求下f(k)

dp啊!

dp[u][x]表示u的子树里选了x对子孙后代点对,然后你会发现我们转移就是一个背包卷一下

...饿他好像就做完了?

完结散花

T1:

code:

#include<cstring>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int p1, p2, k;

inline int gcd(int a, int b) {
	return (b == 0) ? (a) : (gcd(b, a % b));
}

signed main() {
	// freopen("color.in", "r", stdin);
	// freopen("color.out", "w", stdout);
	int T;
	scanf("%lld", &T);
	while(T-- > 0) {
		scanf("%lld%lld%lld", &p1, &p2, &k);
		if(p1 > p2)swap(p1, p2);
		int st = gcd(p1, p2);
		if(k == 1 && p1 == p2) {
			puts("No");
			continue;
		}
		if ((k - 1)*p1 + st < p2)puts("No");
		else puts("Yes");
	}
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
#define ll long long
const int P = 1e9 + 7;
const int MAXN = 5e6 + 7;
vector<int> v;
int pre[MAXN], a[MAXN], n;
struct rec {
	int sum;
	ll ans, suf;
	rec(): sum(0), ans(0) {};
} tr[MAXN * 2];

namespace seg {
#define mid ((l+r)>>1)
	int ls[MAXN], rs[MAXN], root, T;
	inline rec pushup(rec ls, rec rs, int len) {
		rec qwq;
		// printf("%d %d %d %d  %d %d %d ", ls.sum, rs.sum, ls.ans, rs.ans, ls.suf, rs.suf, len);
		qwq.suf = ((rs.suf + 1ll * len * rs.sum % P) % P + ls.suf) % P;
		qwq.ans = ((ls.ans + rs.sum * rs.sum * 1ll * len % P) % P + rs.ans) % P;
		(qwq.ans += 2 * ls.suf % P * rs.sum % P) % P;
		qwq.sum = ls.sum + rs.sum;
		return qwq;
	}
	inline void modify(int &k, int l, int r, int pos, int val) {
		if(!k)k = ++T;
		if(l == r) {
			// printf("%d %d %d\n", l, r, pos);
			tr[k].sum += val;
			tr[k].suf = tr[k].sum;
			tr[k].ans = tr[k].sum * tr[k].sum % P;
			// printf("%d %d %d\n", tr[k].ans, tr[k].sum, tr[k].suf);

			return ;
		}
		if(pos <= mid)modify(ls[k], l, mid, pos, val);
		else modify(rs[k], mid + 1, r, pos, val);
		// printf("!@#%d %d\n", l, r);
		tr[k] = pushup(tr[ls[k]], tr[rs[k]], mid + 1 - l);
		// printf(" !!%d %d\n", tr[k].ans, tr[k].sum);
	}
	inline rec query(int k, int l, int r, int L, int R) {
		if(L <= l && r <= R) {
			return tr[k];
		}
		if(L > mid)return query(rs[k], mid + 1, r, L, R);
		if(R <= mid)return query(ls[k], l, mid, L, R);
		return pushup(query(ls[k], l, mid, L, R), query(rs[k], mid + 1, r, L, R), mid + 1 - l);
	}
#undef mid
}

inline int getid(int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

inline void init() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1; i <= n; ++i) {
		a[i] = getid(a[i]);
		// printf("%d\n", a[i]);
	}
	return;
}

signed main() {
	// freopen("sequence.in", "r", stdin);
	// freopen("sequence.out", "w", stdout);

	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		v.push_back(a[i]);
	}
	init();
	memset(pre, -1, sizeof(pre));

	ll A = 0;
	for(int i = 1; i <= n; ++i) {
		if(pre[a[i]] != -1)
			seg::modify(seg::root, 1, n, pre[a[i]], -1);
		seg::modify(seg::root, 1, n, i, 1);
		pre[a[i]] = i;
		rec tmp = seg::query(seg::root, 1, n, 1, i);
		// printf("\n%d^ %d?\n", tmp.sum, tmp.ans);
		A = (A + tmp.ans) % P;
	}
	printf("%lld\n", A);
	return 0;
}

#include<bits/stdc++.h>
#define add(x,y) (ct(x,y),ct(y,x))
using namespace std;
#define int long long
#define ll long long
const int MAXN = 5050, P = 998244353;
int n, m, siz[MAXN], siz1[MAXN], sz[MAXN], c[MAXN][MAXN], A[MAXN], B[MAXN];
int dp[MAXN][MAXN], ccnt;
int home[MAXN * 2], nxt[MAXN * 2], to[MAXN * 2];
char s[MAXN];


inline void ct(const int &u, const int &v) {
	ccnt++;
	nxt[ccnt] = home[u];
	home[u] = ccnt;
	to[ccnt] = v;
}

inline void dfs(int u, int F) {
	dp[u][0] = 1;
	sz[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		// printf("%d %d\n", u, v);
		if(v == F)continue;
		dfs(v, u);
		vector<int> tmp(sz[u] + sz[v] + 1);
		for(int i = 0; i <= sz[u]; ++i) {
			for(int j = 0; j <= sz[v]; ++j) {
				tmp[i + j] = (tmp[i + j] + 1ll * dp[u][i] * dp[v][j] % P) % P;
			}
		}
		sz[u] += sz[v];
		siz[u] += siz[v];
		siz1[u] += siz1[v];
		for(int i = 0; i <= sz[u]; ++i)dp[u][i] = tmp[i];
	}
	// printf("%d %d %d %d\n", u, sz[u], siz[u], siz1[u]);
	if(s[u] == '0') {
		++siz[u];
		for(int i = siz1[u] - 1; i >= 0; --i) {
			dp[u][i + 1] = (dp[u][i + 1] + dp[u][i] * 1ll * (siz1[u] - i) % P) % P;
		}
	} else {
		++siz1[u];
		for(int i = siz[u] - 1; i >= 0; --i) {
			dp[u][i + 1] = (dp[u][i + 1] + dp[u][i] * 1ll * (siz[u] - i) % P) % P;
		}
	}
}

inline void inv(int *A, int *B, int n) {
	for(int i = 0; i <= n; ++i) {
		for(int d = i; d <= n; ++d) {
			if((d - i) & 1)B[i] = (B[i] - c[d][i] * 1ll * A[d] % P + P) % P;
			else B[i] = (B[i] + c[d][i] * A[d] % P) % P;
		}
	}
}

signed main() {
	cin >> m;
	cin >> (s + 1);
	n = m / 2;
	for(int i = 1; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	dfs(1, 0);
	c[0][0] = 1;
	vector<int> Pw(m + 1);
	Pw[0] = 1;
	for(int i = 1; i <= m; ++i)Pw[i] = Pw[i - 1] * 1ll * i % P;
	for(int i = 1; i <= m; ++i) {
		c[i][0] = c[i][i] = 1;
		for(int j = 1; j < i; ++j) {
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
		}
	}
	for(int i = 0; i <= n; ++i)A[i] = 1ll * dp[1][i] * Pw[n - i] % P;// printf("%d??\n", A[i]);
	inv(A, B, n);
	for(int i = 0; i <= n; ++i)printf("%d\n", B[i]);
}

夏晓光(loveJY)的博客

P6187 [NOI Online Round1 提高组]最小环（民间数据）