夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

CSP-S2考前综合强化刷题（第六场）

2020-10-06 13 min read # 有标号无标号 # 计数题 # 状态压缩 # 比赛题 # 动态规划

三年金牌的题就是难啊

A

gcd(pa−1,pb−1)gcd(p^a-1,p^b-1)

首先有一个结论:

pa−1∣(pka−1)p^a-1|(p^{ka}-1)

证明:

an−bn=(am−bm)(an−m+an−m−1b+an−m−2b2....+a∗bn−m−1+bn−m)a^{n}-b^n=(a^m-b^m)(a^{n-m}+a^{n-m-1}b+a^{n-m-2}b^2....+a*b^{n-m-1}+b^{n-m})

就很显然了

然后就是

gcd(pa−1,pka+b−1)gcd(p^a-1,p^{ka+b}-1)

gcd(pa−1,pb−1+pb(pka−1))gcd(p^a-1,p^{b}-1+p^{b}(p^{ka}-1))

gcd(pa−1,pb−1)gcd(p^a-1,p^{b}-1)

不难发现答案是p(gcd(a,b))−1p^{(gcd(a,b))}-1

code


#include<bits/stdc++.h>
#define ll long long
using namespace std;

int T;
ll p, q, a, b;

inline ll ksm(ll x, ll y, ll p) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % p;
		x = x * x % p;
		y >>= 1;
	}
	return ans;
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%lld%lld%lld%lld", &q, &a, &b, &p);
		if(q == 2 && __gcd(a, b) == 1)puts("1");//当gcd为1的时候我们应该输出1,而不是0
		else printf("%lld\n", ksm(q, __gcd(a, b), p) - 1);
	}
	return 0;
}

B

开1e6个指针,然后每次向下跳,

根据调和级数复杂度O(nlnn)O(nln n)


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 7;
int n, m, a[MAXN], b[MAXN], ans[MAXN];
int M;
int vis[MAXN], id[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; ++i) {
		b[i] = read();
		M = max(M, b[i]);
		vis[b[i]] ++;
	}
	m = read();
	for(int i = 1; i <= m; ++i) {
		a[i] = read();
	}
	for(int i = 1; i <= M; ++i) {
		id[i] = i;
	}
	int k = 0;
	for(int i = 1; i <= m; ++i) {
		for(int &j = id[a[i]]; j <= M; j += a[i]) {
			if(vis[j]) {
				vis[j]--;
				ans[i] = j;
				break;
			}
		}
		if(!ans[i]) {
			k = i - 1;
			break;
		}
	}
	printf("%d\n", k);
	for(int i = 1; i <= k; ++i) {
		printf("%d ", ans[i]);
	}
	puts("");
	return 0;
}

C

拉格朗日恒等式

∑iai2∑ibi2=(∑iaibi)2+∑1<=i<j<=nai∗bj−aj∗bi2\sum_i{a_i^2}\sum_i{b_i^2}=(\sum_i{a_ib_i})^2+\sum_{1<=i<j<=n}{a_i*b_j-a_j*b_i}^2

直接维护三个和即可qwq,可以树状数组

∑1<=i<j<=nai∗bj−aj∗bi2\sum_{1<=i<j<=n}{a_i*b_j-a_j*b_i}^2

拆开

∑1<=i<j<=nai∗bj2+∑1<=i<j<=naj∗bi2−2∗∑1<=i<j<=nai∗bjaj∗bi\sum_{1<=i<j<=n}{a_i*b_j}^2 + \sum_{1<=i<j<=n}{a_j*b_i}^2 - 2*\sum_{1<=i<j<=n}{a_i*b_ja_j*b_i}

做完了,时间复杂度O(nlog2n)O(nlog^2n)

为什么O(log^2n)?因为我们合并的时候要维护

  1. ai∗bja_i*b_j和
  2. aj∗bia_j*b_i和
  3. aia_i和
  4. bib_i和
  5. ai∗bi∗aj∗bja_i*b_i*a_j*b_j和
  6. ai2a_i^2和
  7. bi2b_i^2和

qwq

上述结论证明?....等等吧在推了在推了

好像直接推推就行了吧?


#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 6e5 + 7;
const int MAXT = 1e6 + 1e5;
struct rec {
	ll sa, sb, sa2, sb2, sab, sba, sab2, sba2;
	rec(ll x = 0, ll y = 0, ll z = 0, ll w = 0, ll k = 0, ll g = 0, ll q = 0, ll p = 0): sa(x), sb(y), sa2(z), sb2(w), sab(k), sba(g), sab2(q), sba2(p) {};
} tr[MAXT];
int ls[MAXT], rs[MAXT];
int rt, T, n, q;
int a[MAXN], b[MAXN];
inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}
inline rec merge(rec x, rec y) {
	rec z;
	add(z.sba, x.sab * y.sab % P);add(z.sab2, x.sa2 * y.sb2 % P);add(z.sba2, x.sb2 * y.sa2 % P);
	add(z.sa, x.sa);add(z.sa, y.sa);
	add(z.sb, x.sb);add(z.sb, y.sb);
	add(z.sa2, y.sa2);add(z.sa2, x.sa2);
	add(z.sb2, y.sb2);add(z.sb2, x.sb2);
	add(z.sab2, x.sab2);add(z.sab2, y.sab2);
	add(z.sba2, x.sba2);add(z.sba2, y.sba2);
	add(z.sab, x.sab);add(z.sab, y.sab);
	add(z.sba, x.sba);add(z.sba, y.sba);
	return z;
}
#define mid ((l+r)>>1)
inline void build(int &k, int l, int r) {
	if(!k)k = ++T;
	if(l == r) {tr[k].sa = a[l];tr[k].sb = b[l];tr[k].sa2 = 1ll * a[l] * a[l] % P;tr[k].sb2 = 1ll * b[l] * b[l] % P;tr[k].sab = 1ll * a[l] * b[l] % P;return ;}
	build(ls[k], l, mid);build(rs[k], mid + 1, r);tr[k] = merge(tr[ls[k]], tr[rs[k]]);
}

inline rec query(int k, int l, int r, int L, int R) {
	if(L <= l && r <= R)return tr[k];
	if(R <= mid)return query(ls[k], l, mid, L, R);
	else if(L > mid)return query(rs[k], mid + 1, r, L, R);
	else return merge(query(ls[k], l, mid, L, R), query(rs[k], mid + 1, r, L, R));
}

ll x, y;

inline void modify(int k, int l, int r, int pos) {
	if(l == r) {tr[k].sa = x;tr[k].sb = y;tr[k].sa2 = x * x % P;tr[k].sb2 = y * y % P;tr[k].sab = x * y % P;return ;}
	if(pos <= mid)modify(ls[k], l, mid, pos);
	else modify(rs[k], mid + 1, r, pos);
	tr[k] = merge(tr[ls[k]], tr[rs[k]]);
}

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {p1 = buf;pend = buf + fread(buf, 1, BUF_SIZE, stdin);}return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;
int main() {
	n = read();
	q = read();
	for(int i = 1; i <= n; ++i)a[i] = read();
	for(int i = 1; i <= n; ++i)b[i] = read();
	rt = 1;T = 1;build(rt, 1, n);
	for(int i = 1, opt, l, r, p; i <= q; ++i) {
		opt = read();
		if(opt == 1) {l = read(); r = read(); rec tmp = query(rt, 1, n, l, r);printf("%lld\n", ((tmp.sab2 - 2 * tmp.sba % P + tmp.sba2) % P + P) % P);
		} else {p = read(); l = read(); r = read(); x = l; y = r;modify(rt, 1, n, p);}
	}
	return 0;
}

D

呜呜呜呜呜呜计数

转换问题:(ljh)贡献

有n个变量aia_i每个变量有m中取值,然后有些限制是ai<=bia_i<=b_i

考虑dp出所有元素可行的大小关系,然后分配权值直接用组合数

状压dp

fi,Sf_{i,S}表示S集合内的数比其他数都小,然后只考虑了前i种权值

然后转移的时候枚举其他的一个子集,让他们的权值相同,把它划分进去,然后快速的判断能否划分,就是能否合法转移满足所有限制

dp结束后我们来个插板法,你会发现我们只需要插出i种不同权值....到底哪些相同不重要....

所以就是∗C(i,n)*C(i,n)这个东西

然后就做完了

其实本质上还是一个dp形态最后分配标号的套路


#include<bits/stdc++.h>
using namespace std;
const int MAXM = 25;
const int MAXS = (1 << 16) + 1;
int n, m, P;
int szq[MAXM], szp[MAXM], lmp[MAXS], lmq[MAXS];
int dp[MAXS][MAXM];

inline void add(int &x, int y) {
	x += y;
	x = x >= P ? x - P : x;
}

int main() {
	scanf("%d%d%d", &n, &m, &P);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &szp[i]);
		for(int j = 1, x; j <= szp[i]; ++j) {
			scanf("%d", &x);
			lmp[1 << i - 1] |= (1 << x - 1);
		}
		scanf("%d", &szq[i]);
		for(int j = 1, x; j <= szq[i]; ++j) {
			scanf("%d", &x);
			lmq[1 << i - 1] |= (1 << x - 1);
		}
	}
	int MAS = (1 << n) - 1;
	for(int S = 0; S <= MAS; ++S) {
		for(int i = 1; i <= n; ++i) {
			if(S >> (i - 1) & 1) {
				lmp[S] |= lmp[1 << i - 1];
				lmq[S] |= lmq[1 << i - 1];
			}
		}
	}
	dp[0][0] = 1;
	for(int S = 1; S <= MAS; ++S) {
		for(int T = (S - 1)&S ; ; T = (T - 1)&S) {
			if((lmp[S ^ T]&S) == lmp[S ^ T] && (lmq[S ^ T]&T) == 0) {
				for(int i = 0; i < n; ++i) {
					add(dp[S][i + 1], dp[T][i]);
				}
			}
			if(!T)break;
		}
	}
	int ans = 0, cur = 1;
	static int st[233];
	int sz = 0;
	for(int i = 0; i <= n; ++i) {
		cur = 1;
		for(int j = 1; j <= sz; ++j)
			cur = 1ll * cur * st[j] % P;
		add(ans, 1ll * dp[MAS][i] *cur % P);
		st[++sz] = m - i;
		int tmp = i + 1;
		for(int j = 1; j <= sz; ++j) {
			int g = __gcd(tmp, st[j]);
			tmp /= g;
			st[j] /= g;
		}
	}
	cout << ans << endl;
	return 0;
}
Powered by Gridea RSS