qbxtD8 && NOIP提高组考前刷题冲刺班（第八场）

直接做

注意答案和0取max

从最后一个区间向前考虑,每个区间和前面区间有交集则要向前延伸

然后每个区间一开始左端点为 $ddl time-t$

直接暴力dp的话

$f_{i,j}$ 表示前i个数,最后一个数以j结尾的权值之和

这个转移的复杂度为 $nlnn$ ,并不优秀

如果j和k互质,那么我们有 $f_{i,j}*f_{i,k}=f_{i,j*k}$

然后你会发现我们就能线性筛了QAQ.....

本质上相当于我们把两个数写成质因数乘积

然后对于一个长度为n的序列,每个指数是单调不降的

乘起来相当于每个序列延长一下

然后我们就会发现这个东西可以线性筛了.....

复杂度 $O(nm)$

如果我们预处理所有质数对于n的单独贡献,可以做到 $O(m+nm/lnm)$

code:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + 5;
const int P = 1e9 + 7;
const int MAXN = 24;
const int MAXP = 664591;
bool vis[N];
int prim[N], num[N], mx[N], cnt, n, m;
int fst1[MAXP][MAXN], rc[MAXP];
int f[MAXP][MAXN], g[MAXP][MAXN], sum[MAXN], dp[N];
//我们只需要知道最小质因子
inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}
void init1() {
	cnt = 0;
	for (int i = 2 ; i <= m; ++i) {
		if (!vis[i]) {
			prim[++cnt] = i;
			num[i] = 1;
			mx[i] = cnt;
		}
		for (int j = 1 ; j <= cnt && i * prim[j] <= m; ++j) {
			vis[i * prim[j]] = 1;
			mx[i * prim[j]] = j;
			if (!(i % prim[j])) {
				num[i * prim[j]] = num[i] + 1;
				break;
			}
			num[i * prim[j]] = 1;
		}
	}
	ll V;
	for(int i = 1; i <= cnt; ++i) {
		V = 1;
		for(int j = 0; V <= m; ++j) {
			fst1[i][j] = V;
			rc[i] = j;
			V = V * prim[i];
		}
	}
}
inline void init2() {
	for(int q = 1; q <= cnt; ++q) {
		for(int i = 0; i <= rc[q]; ++i)sum[i] = 1;
		f[q][0] = 1;
		for(int i = 1; i <= n; ++i) {
			for(int j = 0; j <= rc[q]; ++j) {
				add(g[q][j], 1ll * sum[j] * fst1[q][j] % P);
			}
			f[q][0] = g[q][0];
			g[q][0] = 0;
			sum[0] = f[q][0];
			for(int j = 1; j <= rc[q]; ++j) {
				f[q][j] = g[q][j];
				sum[j] = sum[j - 1];
				add(sum[j], f[q][j]);
				g[q][j] = 0;
			}
		}
		for(int j = 1; j <= rc[q]; ++j)
			dp[fst1[q][j]] = f[q][j];
	}
	return ;
}

//题目加强了
inline void solve() {
	int ans = 1;
	dp[1] = 1;
	for(int i = 2; i <= m; ++i) {
		dp[i] = 1ll * dp[fst1[mx[i]][num[i]]] * dp[i / fst1[mx[i]][num[i]]] % P;
		add(ans, dp[i]);
	}
	printf("%d\n", ans);
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	init1();
	init2();
	solve();
	return 0;
}

李队的杜教筛

很慢!

code:


#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define R register
#define ll long long
using namespace std;
const ll P = 1e9 + 7;
const ll MAXP = 4e5 + 7;
const ll mP = 4e5;
const ll N = 1e7 + 7;
ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1) ans *= x, ans %= P;
		x *= x, x %= P, y >>= 1;
	}
	return ans;
}
ll f[12][MAXP];
int m, n;
int q[N][10];
map<ll, ll> dp[11];
ll solve(ll x, ll y) {
	if(y == 1) return q[x][n - 1]; //sigma(x)
	if(x <= mP) return f[y][x];
	if(dp[y][x]) return dp[y][x];
	R ll X = 0, i, j, t, p;
	for(i = 1; i <= x; i = j + 1) {
		t = x / i;
		j = x / t;
		p = q[j][n - y] - q[i - 1][n - y];
		X += p * solve(t, y - 1) % P;
		X %= P;
	}
	X += P, X %= P;
	dp[y][x] = X;
	return X;
}
int main() {
	scanf("%d%d", &n, &m);
	ll tp = mP;
	R ll i, j, k, o, p;
	f[0][1] = 1;
	for(i = 1; i <= m; ++i) {
		q[i][0] = i;
		for(j = 1; j < n; ++j) q[i][j] = 1ll * q[i][j - 1] * i % P;
	}
	for(i = 1; i <= n; ++i) {
		for(j = 1; j <= tp; ++j) {
			p = tp / j;
			for(k = 1; k <= p; ++k) {
				o = k * j;
				f[i][o] += f[i - 1][j] * q[k][n - i] % P;
				f[i][o] %= P;
			}
		}
	}
	for(i = 1; i <= n; ++i) {
		for(j = 1; j <= tp; ++j) {
			f[i][j] += f[i][j - 1];
			f[i][j] %= P;
		}
	}
	for(i = 0; i < n; ++i)
		for(j = 1; j <= m; ++j) {
			q[j][i] += q[j - 1][i];
			q[j][i] -= q[j][i] >= P ? P : 0;
		}
	ll ans = solve(m, n);
	printf("%lld\n", ans);
	return 0;
}

删一条边 : 割边

删两条边

G不连通
G连通

先枚举一条边干掉

拉出生成树(dfs树)T

$e1,e2$ 被完全相同的非树边覆盖了

a树边+非树边

e1不被覆盖

e1只被e2覆盖

b树边加树边

e1,e2被一样的覆盖

e1,e2不被一样的覆盖

给每条非树边一个随机权值,然后让树边的到一个所有的覆盖的非树边异或值

那么我们会发现第一种情况case1

树上一条边权值直接是0

case 2

树上一条边和其他的边权值相同

第二种情况case 3

树上两条边权值相同

此时删掉之后我们至少有一个点留出来?

case 4

树上两条边权值不同

删掉之后不会有影响

所以说我们只需要树上差分之后开个map统计一下即可

时间复杂度 $O(m^2logm))$

py乘

$ (A1e4+B)(C1e4+D)=AC1e8+(AD+BC)*1e4+BD $

$ AD+BC=(A+B)(C+D)-AC-BD $

只需要三次乘法

T(n)=3T(n/2)+O(n)

$n^{1.58}$

阿狸和桃子的游戏

....考...

夏晓光(loveJY)的博客

qbxtD8 && NOIP提高组考前刷题冲刺班（第八场）

qbxtD7 && NOIP提高组考前刷题冲刺班（第七场）