Post 64

Veröffentlicht am | Edited on

Once ， more ， you open the door ， And you’re here in my heart.

把某道测试题拿出来用OGF做一做。

$ordinary ~generating ~function$

img

We construct a OGF for the combination of $m$ stores.

Appearantly , the money is combinated by the sum of stores. And the choices are the Multiply principle of combination.

We let $F(x) = \prod{k=1}^{m}\sum{i=0}^{w_i}x^i$

Each polymial is a choice for a store.

The coefficient of $x^k$ is the $k$ dollors ‘ number of scheme.

The $n-m$ stores could be calculated by $plate ~insertion ~method$ , which is a classical method in math.

But a store could contribute 0 dollar.
We could create imagination balls…..(I do not understand actually)

Then we just need to expand the polymial , enumerates $t$ for the dolllars the $m$ stores contributed of $f_t$ , the remain $k-t$ dollars are from $n-m$ stores , use $plate ~insertion ~method$.

the answer is $\sum{t=0}^{k}f_tC{k-t+n-m-1}^{n-m-1}$

Time complexity is $O(m^4 + k)$

firstly I think it is $O(m^3)$ , then I got TLE…

Use $NTT $ could optimize it by $O(m^2logm + k)$

70pts Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxk 5000005
#define maxn 5000005
const int mod = (int)1e9+7;

int f[90005] , fac[maxk+maxn] , n , m , w[305] , k , tmp[90005] , s , ans , v[maxn+maxk];
int cnt;
inline void ogf() // this might be O(m^4)....
{
	s = w[1];
	for(int i = 0 ; i <= w[1] ; ++i) f[i] = 1;

	for(int i = 2 ; i <= m ; ++i)
	{
	//	if(w[i] == 0) continue;
		for(int j = 0 ; j <= s ; ++j)
			tmp[j] = f[j] , f[j] = 0;

		for(int j = 0 ; j <= w[i] ; ++j)
			for(int t = 0 ; t <= s ; ++t)
				(f[j + t] += tmp[t]) %= mod , ++cnt;
		s += w[i];
	}
	printf("COMS : %d\n",cnt);
}

inline void dp()
{
	f[0] = 1;
	for(int i = 1 ; i <= m ; ++i)
	{
		s += w[i];
		for(int j = s ; ~j ; --j)
			for(int t = 0 ; t <= w[i] ; ++t)
				f[j + t] += f[t];
	}
	for(int i = 1 ; i <= s ; ++i)
		printf("%d ",f[i]);
}
int inv(int x)
{
	if(x == 1) return 1;
	return 1ll * (mod - mod / x) * inv(mod % x) % mod;
}

inline int C(int n , int m){
	return 1ll * fac[n] * v[m] % mod * v[n-m] % mod;
}

int main()
{
//	freopen("shopping.in","r",stdin);
//	freopen("shopping.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d",&w[i]);
//	ogf();
	dp();
	fac[0] = 1;
	for(int i = 1 ; i <= n + k  ; ++i)
		fac[i] = 1ll * fac[i-1] * i % mod;
	if(n == m){
		printf("%d\n",f[k]);
		return 0;
	}
	v[n + k] = inv(fac[n + k]);
	for(int i = n + k - 1 ; i >= 1 ; --i)
		v[i] =  1ll * v[i+1] * (i + 1) % mod;
	int t = std::min(s,k);
	for(int i = 0 ; i <= t ; ++i)
		(ans += 1ll * f[i] * C(k - i + n - m - 1 , n - m -1) % mod) %= mod;
	printf("%d\n",ans);
}

然后又开始处于待机状态。。luogu上看了几道CF黑题发现就一道不会（你谷不是人均AK IOI？）

CF891C Envy

题意翻译

给出一个nn 个点mm条边的无向图，每条边有边权，共$Q$次询问，每次给出$k_i$条边，问这些边能否同时在一棵最小生成树上。

题解

求任意最小生成树，树上倍增（或者HPD）然后每次查询边两点的链上最小值，如果相等就继续，大于就GG,不存在小于的情况，套路题？

CF893F Subtree Minimum Query

题意翻译

题目大意：

给你一颗有根树，点有权值，m次询问，每次问你某个点的子树中距离其不超过k的点的权值的最小值。（边权均为1，点权有可能重复，k值每次询问有可能不同，强制在线）

真实询问计算方法：

x=(x′+lans)modn+1;

k=(k′+lans)modn;

数据范围： n<=100000,ai<=10^9,m<=1000000

题解

时限这么长，就不能树分块直接$O(n\sqrt{n})$艹过去么呵呵。

BFS建权值主席树，二分AC

哦不，强制在线！！！

然后想了半天考虑了DFS序考虑了BFS序但是都不行。

然后正解就是两个的结合。。。DFS序为可持久化权值线段树下标，BFS序为时间轴一个一个加点。

然后对深度个数求前缀和，二分出权值线段树的时间轴区间 ，查询下标区间$[dfn_x , dfn_x＋sz_x]$的最小值即可。

时间/空间复杂度$O((n+m)logn)$

这道题很棒啊。