Post 64

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)$

这道题很棒啊。