Codeforces Round#728 div.1+div.2题解_inta=10)15a+=(a+=5,a*2,a-=5); printf ("%d",a);

div.2 视频讲解：BV19f4y1t7En
div.1 视频讲解：BV1io4y1C7Dd

div.2-A. Pretty Permutations

题目大意

有 $n$ 只猫排成一排，标记为 $1$ 到 $n$ ，第 $i$ 只猫位于位置 $i$ 。 他们厌倦了整天在同一个地方打转，所以他们想重新安排自己，这样猫就不会像以前一样在同一个地方了。 他们也很懒惰，所以他们想尽量减少他们移动的总距离。 帮助他们决定在重新排序后每个位置应该放什么猫。

例如，如果有 $3$ 只猫，这是一个有效的重新排序：$[3,1,2]$ 。 没有猫在原来的位置。 猫移动的总距离为 $1+1+2=4$ ，因为猫 $1$ 向右移动一位，猫 $2$ 向右移动一位，而猫 $3$ 向左移动两位。

题解

贪心可得，相邻交换最优。
若 $n$ 为偶数，则相邻奇偶位交换。
若 $n$ 为奇数，则有三只猫轮换，剩余相邻奇偶位交换。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int main()
{
	int T,n,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n%2)
		{
			printf("3 1 2");
			for(i=4;i<=n;i+=2)
				printf(" %d %d",i+1,i);
				puts("");
		}
		else
		{
			for(i=1;i<=n;i+=2)
				printf("%d %d ",i+1,i);
			puts("");
		}
	}
}
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

div.2-B. Pleasant Pairs

题目大意

给定包含 $n(2\le n\le 2\cdot 10^5)$ 个不同元素的数组 $a_i(1\le a_i\le 2\cdot n)$ ，求满足以下条件的 $(i,j)$ 对：

• $i<j$ ；
• $a_i\ast a_j=i+j$ ；

题解

对于每个 $i$ ，暴力枚举所有 $a_i$ 的倍数然后判断即可，注意 $i\ne j$ 。
复杂度可以用调和级数证明为 $O(n\cdot log(n))$ 。

参考代码

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

const int MAXN=100100;
int a[MAXN];
map<int,int> mp;

int main()
{
	int T,n,i,j,k,ans;
	scanf("%d",&T);
	while(T--)
	{
		mp.clear();
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			mp[a[i]]=i;
		}
		ans=0;
		for(i=1;i<=n;i++)
		{
			for(k=a[i];k<=2*n;k+=a[i])
			{
				j=mp[k/a[i]];
				if(j&&j^i)
					ans+=(k==i+j);
			}
		}
		printf("%d\n",ans/2);
	}
}
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

div.2-C/div.2-A. Great Graphs

题目大意

已知有一张包含 $n(1\le n\le 10^5)$ 个节点的有向图。有向图上每条边有边权值，边权值可能为正也可能为负，不存在负环。
已知节点 $1$ 到每个节点的最短距离 $d_i$ ，求满足条件的图中，边权值总和最小为多少。

题解

边权值总和最小时，必然只有一条正边，指向最远的节点。
同时，每个节点 $i$ 会有负边指向其他更近的节点 $j$ ，权值为 $d_j-d_i(d_j<d_i)$ 。
实现时，对所有距离排序后用前缀和处理即可。

参考代码

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

const int MAXN=100100;
ll d[MAXN],sum[MAXN];

int main()
{
	int T,i,n;
	ll mx,ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%lld",&d[i]);
		sort(d+1,d+n+1);
		for(i=1;i<=n;i++)
			sum[i]=sum[i-1]+d[i];
		ans=d[n];
		for(i=1;i<=n;i++)
			ans+=sum[i-1]-sum[0]-(i-1)*d[i];
		printf("%lld\n",ans);
	}
}
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

div.2-D/div.1-C. Tree Array

题目大意

给定一个包含 $n(2\le n\le 200)$ 个节点的树，对树上的节点进行 $1$ 到 $n$ 编号。
一开始随机选择一个节点，标记为 $1$ 。
之后每次随机选择一个与已被标记的节点相邻的未标记节点，进行标记。直到所有节点都被标记完。
设 $a_i$ 为节点 $i$ 被标记的编号。求数列 $a_i$ 的逆序数对数量的期望。

题解

考虑一对逆序数对 $(i,j)(i<j,a_i>a_j)$ 出现的概率 $P_{i,j}$，则易得总期望为
$$E=\sum _{i=1}^n\sum _{j=i+1}^n{P}_{i,j}$$
以下图为例，假设 $i=A,j=B,A<B$ ，如果希望使得 $a_A>a_B$ ，那么必须先访问到 $B$ 再访问 $A$ 。

有以下三种情况：

1. 若起点在红色区域，则不可能先访问到 $B$ 再访问 $A$ ；
2. 若起点在蓝色区域，则必然先访问到 $B$ 再访问 $A$ ；
3. 若起点在红蓝之间某个节点，例如绿色区域，则有可能先访问到 $B$ 再访问 $A$ ，也有可能先访问到 $A$ 再访问 $B$ ；

对于前两种情况，求子树大小很容易解决。主要考虑第三种情况。
假设起点在绿色区域，首先会有这样一个结论：

• 不论起点在绿色区域哪一点，先访问到 $B$ 再访问 $A$ 的概率都一样。

证明很容易，因为不论起点在绿色区域哪一点，必然先访问 $C$ ，再访问 $A$ 或 $B$。
因此考虑起点在绿色区域时先访问到 $B$ 再访问 $A$ 的概率，等价于将绿色区域都缩点为 $C$ 后的概率。

假设 $A-B$ 链上的节点都没有其他分支（比如紫色区域除 $F$ 节点以外的其他节点），那么先访问到 $B$ 再访问 $A$ 的概率可以转化为：

• 给定两个堆，每堆中分别有 $x$ 个和 $y$ 个元素。每次等概率的选取一个堆，然后删掉其中的一个元素。求第一个堆先被删除完的概率。

其中 $x$ 和 $y$ 分别为 $C$ 到 $B$ 和 $A$ 的距离。

这个问题可以用概率DP求解。设 $d{p}_{x,y}$ 表示删完第一个堆的概率，则有：
$$d{p}_{x,y}=\frac{d{p}_{i-1,j}+d{p}_{i,j-1}}{2}$$
初始 $d{p}_{0,i}=1,d{p}_{i,0}=0,d{p}_{0,0}=1(1\le i\le n)$ 。

但是 $A-B$ 链上的节点可能有其他分支，例如 $F$ 节点有紫色区域的分支。
观察后会发现，分支节点对访问到 $B$ 再访问 $A$ 的概率无影响，因为其等价于新增一些其他堆，而其他堆不影响第一个堆先被删完还是第二个堆先被删完。

综上，$P_{i,j}$为：

$$P_{i,j}=\sum _{k\in Link(i,j)}d{p}_{dis(j,k),dis(i,k)}\ast \frac{siz{e}_k}{n}$$

其中 $dis(x,y)$ 表示 $x$ 节点与 $y$ 节点的距离， $siz{e}_k$ 表示链 $Link(i,j)$ 上 $k$ 节点所在分支的大小。

实现时，可以用 dfs 或 lca 遍历链上节点。

参考代码

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

const int MAXN=220;
const ll mod=1e9+7;
int n,siz[MAXN],dsum[MAXN];
ll ans,inv[MAXN],dp[MAXN][MAXN];
vector<int> e[MAXN];

ll powmod(ll x,ll p)
{
	ll ret=1;
	while(p)
	{
		if(p&1)
			ret=ret*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ret;
}

void dfs1(int x,int fa)
{
	siz[x]=1;
	for(int i=0;i<e[x].size();i++)
	{
		int son=e[x][i];
		if(son==fa)
			continue;
		dfs1(son,x);
		siz[x]+=siz[son];
	}
}

ll frac(ll x,ll y)
{
	return x*inv[y]%mod;
}

void dfs2(int x,int fa,int d,int root)
{
	if(x<root)
	{
		for(int i=0;i<=d-1;i++)
			ans=(ans+frac(dsum[i],n)*dp[i][d-i]%mod)%mod;
	}
	for(int i=0;i<e[x].size();i++)
	{
		int son=e[x][i];
		if(son==fa)
			continue;
		dsum[d]=siz[x]-siz[son];
		dfs2(son,x,d+1,root);
	}
}

int main()
{
	int i,j,x,y;
	for(i=1;i<MAXN;i++)
		inv[i]=powmod(i,mod-2);
	dp[0][0]=1;
	for(i=1;i<MAXN;i++)
	{
		dp[0][i]=1;
		dp[i][0]=0;
	}
	for(i=1;i<MAXN;i++)
		for(j=1;j<MAXN;j++)
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])*inv[2]%mod;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	ans=0;
	for(i=1;i<=n;i++)
	{
		dfs1(i,-1);
		dfs2(i,-1,0,i);
	}
	printf("%lld\n",ans);
}
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
78
79
80
81
82
83
84
85
86
87

div2-E1+E2/div1-C1+C2. Converging Array

题目大意

有一个程序会对长度为 $n(2\le n\le 100)$ 的数组 $a$ 和长度为 $n-1$ 的数组 $b$ 进行操作。操作次数为无穷多，每次操作具体如下：

1. 随机选择一个整数 $i(1\le i\le n-1)$ ；
2. 修改： $a_i=min(a_i,\frac{a_i+a_{i+1}-b_i}{2})，a_{i+1}=max(a_{i+1},\frac{a_i+a_{i+1}+b_i}{2})$ 。修改时无四舍五入操作，即有可能变为非整数。

最终 $a_i$ 会分别收敛到某一值。设 $F(a,b)$ 为收敛后的 $a_1$ 。

给定数组 $b$ ，但不确定数组 $a$ 。但知道数组 $c$ ，使得数组 $a$ 是整数数组且 $0\le a_i\le c_i(1\le i\le n)$。
求满足条件的 $F(a,b)\ge x$ 的数组 $a$ 的数量。

每次询问给定一个 $x$ ,
对于 Easy Version，只有一次询问；
对于 Hard Version，有 $q(1\le q\le 10^5)$ 次询问。

题解

参考 官方 和 syksykCCC 的题解与 sd0061 的代码。

当 $a$ 收敛时，数组 $a$ 不再变化，会有 $a_{i+1}-a_i=max(b_i,a_{i+1}-a_i)$ 。
也就是说在收敛之前，每次选择 $i$ 进行操作时，都会同时改变 $a_i$ 和 $a_{i+1}$ ，直到 $a_{i+1}-a_i\ge b_i$ 。

设 $f_i$ 表示最终收敛的数组。

有以下显然的结论：

1. 如果在程序运行过程中，如果 $a_{i+1}-a_i\le b_i$ ，则 $f_{i+1}-f_i=b_i$ 。如果 $f_{i+1}-f_i>b_i$ 则选择 $i$ 的操作不会修改数组 $a$ 。
2. 如果选择 $i$ 的操作不会修改数组 $a$ ，则可以视为 $[1,i]$ 和 $[i+1,n]$ 是相互独立不影响的。
3. 如果选择 $i$ 的操作是第一个不会修改数组的操作，那么 ${\sum }_{j=1}^i{a}_j={\sum }_{j=1}^i{f}_j$ 。因为每次操作修改时， $a_i$ 和 $a_{i+1}$ 的总和不变。

设 $i$ 是第一个不会修改数组的操作，则有：
$$f_1+(f_1+b_1)+(f_1+b_1+b_2)+...+(f_1+\sum _{j=1}^{i-1}{b}_j)=a_1+a_2+a_3+...+a_i$$

设

• $a{p}_i={\sum }_{j=1}^i{a}_j$ ;
• $b{p}_i={\sum }_{j=1}^i{b}_j$ ;
• $bp{p}_i={\sum }_{j=1}^{i}b{p}_j$ ;
• $c{p}_i={\sum }_{j=1}^i{c}_j$ ;

则上式可以写为：
$$i\ast f_1+bp{p}_{i-1}=a{p}_i$$

变化可得：
$$f_1=\frac{a{p}_i-bp{p}_{i-1}}{i}$$

我们可以得到 $f_1=mi{n}_{i=1}^n(\frac{a{p}_i-bp{p}_{i-1}}{i})$ ，证明：

• $f_1\ge mi{n}_{i=1}^n(\frac{a{p}_i-bp{p}_{i-1}}{i})$ ，否则 $f_1$ 就不在集合 { a p i − b p p i − 1 i } \{\frac{ap_i-bpp_{i-1}}{i}\} {iapi​−bppi−1​​} 中、
• $f_1\le mi{n}_{i=1}^n(\frac{a{p}_i-bp{p}_{i-1}}{i})$ ，否则存在 $j(1\le j<i)$ 使得 $f_{j+1}-f_j>b_j$ 即存在更早的分割点。

现在问题就变成了存在多少种序列 $a$ ，满足 $0\le a_i\le c_i$ ，使得 $mi{n}_{i=1}^n(\frac{a{p}_i-bp{p}_{i-1}}{i})\ge x$ 。

设 $d{p}_{i,j}$ 表示前 $i$ 项 $a_i$ 之和为 $j$ 的方案数，那么合法条件就变为 $j\ge x\ast i+bp{p}_{i-1}$ 。
状态转移方程为
$$d{p}_{i,j}=\sum _{k=max(j-c_i,0)}^{j}d{p}_{i-1,k}$$
其中 $max(x\ast i+bp{p}_{i-1},0)\le j\le c{p}_i$ 。
由于转移时求的是区间总和，因此可以用前缀和将每次转移复杂度优化到 $O(1)$ 。

最终答案为：
$$ans=\sum _{j=0}^{c{p}_n}d{p}_{n,j}$$

如果每次询问进行计算，可以在 $O(q{n}^{2}m)$ 的复杂度内得到答案，其中 m = m a x { c i } m=max\{c_i\} m=max{ci​} 。

对于 Easy Version ， $q=1$ 复杂度达标。
对于 Hard Version ，发现：

• 若 $x\le mi{n}_{i=1}^n(\frac{bp{p}_{i-1}}{i})$ ，则必然满足 $x\le mi{n}_{i=1}^n(\frac{a{p}_i-bp{p}_{i-1}}{i})$ ，即答案为 ${\prod }_{i=1}^n{c}_i+1$ ；
• 若 $x>m+mi{n}_{i=1}^n(\frac{bp{p}_{i-1}}{i})$ ，则必然导致 $x>mi{n}_{i=1}^n(\frac{a{p}_i-bp{p}_{i-1}}{i})$ ，无合法情况，答案为 $0$ 。

因此只需求解 $[mi{n}_{i=1}^n(\frac{bp{p}_{i-1}}{i}),mi{n}_{i=1}^n(\frac{bp{p}_{i-1}}{i})+m]$ 范围内的答案即可。
采用预处理或者记忆化，将复杂度降为 $O(n^2{m}^2)$ 。

参考代码

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

const int MAXN=110;
const int mod=1e9+7;
int b[MAXN],c[MAXN],bp[MAXN],bpp[MAXN],cp[MAXN],f[2][2*MAXN*MAXN],ans[MAXN<<1];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=mod)
		x-=mod;
}

int main()
{
	int n,i,j,k;
	int mn,mx,x,q,nxt,cur;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		cp[i]=cp[i-1]+c[i];
	}
	for(i=1;i<n;i++)
	{
		scanf("%d",&b[i]);
		bp[i]=bp[i-1]+b[i];
		bpp[i]=bpp[i-1]+bp[i];
	}
	mn=1<<30;
	for(i=1;i<=n;i++)
		mn=min(mn,-bpp[i-1]/i);
	mx=mn+150;
	mn=mn-45;
	memset(ans,-1,sizeof(ans));
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&x);
		x=min(mx,max(mn,x));
		if(~ans[x-mn])
		{
			printf("%d\n",ans[x-mn]);
			continue;
		}
		cur=1,nxt=0;
		memset(f,0,sizeof(f));
		for(j=0;j<=c[1];j++)
			f[cur][j]=1;
		for(i=1;i<=n;i++)
		{
			memset(f[nxt],0,sizeof(f[nxt]));
			for(j=max(x*i+bpp[i-1],0);j<=cp[i];j++)
			{
				add(f[nxt][j],f[cur][min(cp[i-1],j)]);
				if(j-c[i]-1>=0)
					add(f[nxt][j],mod-f[cur][j-c[i]-1]);
			}
			for(j=1;j<=cp[i];j++)
				add(f[nxt][j],f[nxt][j-1]);
			swap(cur,nxt);
		}
		ans[x-mn]=f[cur][cp[n]];
		printf("%d\n",ans[x-mn]);
	}
}
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

div1-D. Inverse Inversions

题目大意

有一个长度为 $n(1\le n\le 10^5)$ 的排列 $p$ ，但你并不知道它，只知道数组 $b$ ，其中 $b_i$ 表示 $j<i$ 且 $p_j>p_i$ 的 $j$ 数量。

有 $q(1\le q\le 10^5)$ 次询问，询问有两种格式：

• $1ix$ - 将 $b_i$ 修改为 $x(0\le x<i)$ ；
• $2i$ - 输出 $p_i$ ，如果有多解输出任意一个即可；

题解

参考 froggyzhang 的代码。

对于第 $i$ 个元素 $p_i$ ，如果知道共有 $q_i$ 个元素比其大，那么 $p_i=n-q_i$ 。
在前 $i-1$ 个元素中，根据题意可知共有 $b_i$ 个元素比 $p_i$ 大。
在之后的 $n-i$ 个元素中，每增加一个元素 $p_x$ ，有以下两种可能：

• 若 $b_x>q_i$ ，则表示 $p_i>p_x$ ， $q_i$ 不变；
• 若 $b_x\le q_i$ ，则表示 $p_i<p_x$ ，$q_i=q_i+1$ ；

这样，就可以在$O(n)$ 复杂度内求解出 $q_i$ 和 $p_i$ 。

由于存在多次修改和查询，考虑对其分块。
设每块大小为 $B$ ， $p_i$ 所在块的编号为 $po{s}_i$ 。
设 $a_i$ 表示在 $[1,po{s}_i-1]$ 这些块中，比 $p_i$ 大的元素个数。
$a_i=b_i-$ 块内比 $p_i$ 大的元素个数

可以通过树状数组/线段树，在 $O(Blog(n))$ 的复杂度内求出块内比 $p_i$ 大的元素个数，维护每一块内所有的 $a_i$ 。

那么对于任意元素 $p_x$ ，可以分两阶段求解有多少元素大于 $p_x$ ：

• 在 $[1,po{s}_x]$ 这些块，比 $p_x$ 大的元素个数，可以通过原始方法遍历第 $po{s}_i$ 块求得，时间复杂度 $O(B)$ 。
• 在 $[po{s}_x+1,maxBlock]$ 这些块中，比 $p_x$ 大的元素个数，等于每一块内 $a_i\le q_x$ 的数量，可以对每一块用二分求解得到，时间复杂度为 $O(\frac{n}{B}log(B))$ 。

$B=\sqrt{n\cdot log(n)}$ 时最优，总时间复杂度 $O(q\sqrt{n\cdot log(n)})$ 。

参考代码

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

const int MAXN=100100;
int n;
int b[MAXN],l[MAXN],r[MAXN],pos[MAXN],tr[MAXN];
vector<int> v[MAXN];

void add(int x,int d)
{
	while(x<=n)
	{
		tr[x]+=d;
		x+=x&(-x);
	}
}

int find(int x)
{
	int ret=0;
	for(int i=17;i>=0;i--)
	{
		if(ret+(1<<i)<n&&tr[ret+(1<<i)]+(1<<i)<x)
		{
			ret+=1<<i;
			x-=tr[ret]+(1<<i);
		}
	}
	return ret+1;
}

void build(int x)
{
	v[x].clear();
	for(int i=l[x];i<=r[x];i++)
	{
		int p=find(b[i]+1)-1;
		v[x].push_back(p);
		add(p+1,1); 
	}
	for(int i=0;i<v[x].size();i++)
		add(v[x][i]+1,-1);
	sort(v[x].begin(),v[x].end());
}

int main()
{
	int i,j,len,blocks,q,op,x,y,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&b[i]);
	len=min(n,200);
	blocks=n/len;
	if(n%len)
		blocks++;
	for(i=1;i<=blocks;i++)
	{
		l[i]=(i-1)*len+1;
		r[i]=min(n,i*len);
		for(j=l[i];j<=r[i];j++)
			pos[j]=i;
	}
	for(i=1;i<=blocks;i++)
		build(i);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d",&x,&y);
			b[x]=y;
			build(pos[x]);
		}
		else
		{
			scanf("%d",&x);
			ans=b[x];
			for(i=x+1;i<=r[pos[x]];i++)
			{
				if(ans>=b[i])
					ans++;
			}
			for(i=pos[x]+1;i<=blocks;i++)
				ans+=upper_bound(v[i].begin(),v[i].end(),ans)-v[i].begin();
			printf("%d\n",n-ans);
		}
	}
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90

div1-E. Tasty Dishes

题目大意

有 $n(1\le n\le 300)$ 名厨师，编号从 $1$ 到 $n$ 。
厨师 $i$ 的水平为 $i$ ，初始能够做出美味度为 $a_i(|a_i|\le i)$ 的菜。
每位厨师有一个包含其他厨师的学习列表，可以通过学习列表上的其他厨师来提高自己菜的美味度，但只能水平低的厨师向水平高的厨师学习，反之则不行。

每天厨师们会进行两个阶段的学习，来改变菜的美味度：

1. 每一天开始时，每位厨师可以将自己菜肴的美味度变为 $i\ast a_i$ ，也可以保留 $a_i$ 不变。
2. 阶段 $1$ 结束后，每位厨师会学习其列表上的其他厨师。具体而言，对于厨师 $i$ 的列表上的每位厨师 $j$ ，厨师 $i$ 可以向厨师 $j$ 学习，从而使得自己菜肴的美味度变为 $a_i+a_j$ 。厨师 $i$ 也可以选择不向厨师 $j$ 学习，则其菜肴美味度保持 $a_i$ 不变。
   注意这种学习是同时发生的，也就是说厨师 $i$ 向厨师 $j$ 学习后增加的美味度，等于阶段 $1$ 结束时的 $a_j$ 。

每位厨师都会选择使自己菜肴美味度 $a_i$ 更大的选择。

有 $q(1\le q\le 2\cdot 10^5)$ 次询问，每次询问有以下两种格式：

• $1klr$ - 输出在当前初始条件下，第 $k(1\le k\le 10^3)$ 天后的 ${\sum }_{i=l}^r{a}_i$ ；
• $2ix$ - 初始时厨师 $i$ 的菜肴美味度 $a_i$ 增加 $x(1\le x\le 10^3)$ ，即变为 $a_i+x$ ;

题解

参考 官方 和 p_b_p_b 的题解与 ezoilearner 的代码。

由于厨师总是会采用使得美味度最大的策略，因此

• 在阶段 $1$ 中，只有当 $a_i>0$ 时，才会选择将菜肴美味度变为 $i\ast a_i$ ；
• 在阶段 $2$ 中，只有当 $a_j>0$ 时，厨师 $i$ 才会选择学习厨师 $j$ ，使得 $a_i=a_i+a_j$ ；

设 $d_i$ 表示最早第 $d_i$ 天后， $a_i$ 是正数。

• 若初始 $a_i$ 就是正数，则 $d_i=0$ ；
• 若始终无法使得 $a_i$ 为正数，则 $d_i=inf$ ；

注意到题目中有个重要条件，初始 $|a_i|<0$ ，且只能水平低的厨师向水平高的厨师学习。
因此若厨师 $j$ 在厨师 $i(j>i)$ 的学习列表中，某一天开始时，$a_i<0,a_j>0$ ，则当天结束后，$a_i$ 会变成 $a_i+j\ast a_j\ge -i+j\ast 1>0$ ，即 $a_i$ 会变成正数。
故可以得到转移式：
d i = m i n j ∈ L i s t ( i ) { d j + 1 } d_i=min_{j \in List(i)}\{d_j+1\} di​=minj∈List(i)​{dj​+1}

给定初始 $a_i$ ，在 $O(n^2)$ 的复杂度内可以求得所有 $d_i$ 。

如果某一天所有 $a_i$ 都为正数，则从当前天的 { a i } \{a_i\} {ai​} 变化到下一天 { a i } \{a_i\} {ai​} 可以用矩阵乘法实现。
具体而言，设 $\overrightarrow{V_k}$ 表示第 k ( x ≥ m a x { d i } ) k(x \geq max\{d_i\}) k(x≥max{di​}) 天每位厨师菜肴美味值 $a_i$ 构成的 $n$ 维向量，则
$$\overrightarrow{V_{k+1}}=A\cdot \overrightarrow{V_k}$$

其中 $A$ 为 $n\ast n$ 的矩阵，其由以下条件构成：

• $A_{i,i}=i$ ，表示阶段 $1$ 的变化；
• 若厨师 $j$ 在厨师 $i$ 的学习列表上， $A_{i,j}=j$ ，表示阶段 $2$ 的变化；
• 其他位置， $A_{i,j}=0$ ；

设 $\overrightarrow{e_i}$ 表示第 $i$ 个维度为 $1$ 的 $n$ 维单位向量，即 $\overrightarrow{e_i}=(\underset{i-1}{\underbrace{0,\cdots ,0}},1,\underset{n-i}{\underbrace{0,\cdots ,0}}{)}^{\mathrm{T}}$ 。
由于当 $a_i$ 变为正时，会逐渐对厨师 $i$ 的徒子徒孙产生影响，每过一天多影响一辈的徒弟。
因此利用矩阵 $A$ ，分别计算每个初始 $a_i$ 对每个厨师菜肴美味值的贡献，从而求得第 $k$ 天每名厨师菜肴美味值表示的向量 $\overrightarrow{V_k}$ :
$$\overrightarrow{V_k}=\sum _{d_i\le k}{A}^{k-d_i}\overrightarrow{e_i}{a}_i+\sum _{d_i>k}\overrightarrow{e_i}{a}_i$$

这样就有了一个复杂度为 $O(q{n}^4)$ 的解决方案，考虑对其优化。

预习回顾线性代数中关于特征值和特征向量的知识，矩阵的一对特征值 $\lambda$ 和特征向量 $\vec{v}$ 存在以下性质：
$$A\cdot \vec{v}=\lambda \cdot \vec{v}$$
即原先 $O(n^2)$ 的矩阵乘向量变为了$O(n)$ 的常数称向量，考虑以此进行优化。

矩阵 $A$ 的特征值 $\lambda$ 等于以下方程的解：
$$det(A-\lambda I)=0$$

由于题意设定只能水平低的厨师向水平高的厨师学习，因此矩阵 $A$ 是一个上三角矩阵，且对角线上恰好是 $1$ ~ $n$ ，因此：

• 矩阵 $A$ 存在 $n$ 个特征值，恰好是 $1$ ~ $n$ ;
• 方程组 $(A-\lambda I)\vec{x}=\vec{0}$ 可以在 $O(n^2)$ 的复杂度内用高斯消元求解，解得的 $\vec{x}$ 是特征向量；

总计可以在 $O(n^3)$ 的复杂度内用高斯消元求解出所有特征向量。

设特征值 ${\lambda }_i=i$ 对应的特征向量为 $\overrightarrow{v_i}$ 。
利用 $A\cdot \overrightarrow{v_i}={\lambda }_i\cdot \overrightarrow{v_i}$ 的性质，可以在 $O(n\cdot log(k))$ 的复杂度内求得 $A^k\cdot \overrightarrow{v_i}$ 。如果预处理打表的话，则可以降低到 $O(n)$ 。

将 $\overrightarrow{e_i}$ 分解为特征向量 { v i } \{v_i\} {vi​} 的线性组合，这一操作可以看作求 $v_i$ 构成的矩阵的逆，通过类似高斯消元的方式，可以在 $O(n^3)$ 复杂度内求出。
设分解结果为 $\overrightarrow{e_i}={\sum }_{j=1}^n{c}_{i,j}\overrightarrow{v_j}$ 。那么原先的矩阵乘法，可以优化为：
V k ⃗ = ∑ d i ≤ k A k − d i e i ⃗ a i + ∑ d i > k e i ⃗ a i = ∑ d i ≤ k ∑ j = 1 n λ j k − d i ⋅ c i , j ⋅ a i ⋅ v j ⃗ + ∑ d i > k e i ⃗ a i = ∑ j = 1 n λ i k ⋅ v j ⃗ ⋅ ∑ d i ≤ k λ j − d i ⋅ c i , j ⋅ a i + ∑ d i > k e i ⃗ a i

$$\begin{aligned} \vec{V_k} &=\sum_{d_i \leq k}{A^{k-d_i}\vec{e_i}a_i} +\sum_{d_i>k}{\vec{e_i}a_i} \\&=\sum_{d_i \leq k}{\sum_{j=1}^n{\lambda_j^{k-d_i} \cdot c_{i,j} \cdot a_i \cdot \vec{v_j}}}+\sum_{d_i>k}{\vec{e_i}a_i} \\&=\sum_{j=1}^n{\lambda_i^k \cdot\vec{v_j} \cdot\sum_{d_i \leq k}{\lambda_j^{-d_i} \cdot c_{i,j} \cdot a_i}}+\sum_{d_i>k}{\vec{e_i}a_i} \end{aligned}$$ Vk​ ​​=di​≤k∑​Ak−di​ei​ ​ai​+di​>k∑​ei​ ​ai​=di​≤k∑​j=1∑n​λjk−di​​⋅ci,j​⋅ai​⋅vj​ ​+di​>k∑​ei​ ​ai​=j=1∑n​λik​⋅vj​ ​⋅di​≤k∑​λj−di​​⋅ci,j​⋅ai​+di​>k∑​ei​ ​ai​​

a n s ( k , l , r ) = ∑ p = l r V k ⃗ p = ∑ j = 1 n λ i k ⋅ ∑ p = l r v j ⃗ p ⋅ ∑ d i ≤ k λ j − d i ⋅ c i , j ⋅ a i + ∑ p = l r ( d p > k ) ⋅ a i

$$\begin{aligned} ans(k,l,r)&=\sum_{p=l}^r{\vec{V_k}_p} \\&=\sum_{j=1}^n{\lambda_i^k \cdot \sum_{p=l}^r{\vec{v_j}_ p} \cdot\sum_{d_i \leq k}{\lambda_j^{-d_i} \cdot c_{i,j} \cdot a_i}}+\sum_{p=l}^r{(d_p>k) \cdot a_i} \end{aligned}$$ ans(k,l,r)​=p=l∑r​Vk​ ​p​=j=1∑n​λik​⋅p=l∑r​vj​ ​p​⋅di​≤k∑​λj−di​​⋅ci,j​⋅ai​+p=l∑r​(dp​>k)⋅ai​​

其中 ${\sum }_{p=l}^r{\overrightarrow{v_j}}_p$ 可以用前缀和快速求和， ${\sum }_{d_i\le k}{\lambda }_j^{-d_i}\cdot c_{i,j}\cdot a_i$ 可以用树状数组/线段树进行快速求和，将每次询问的复杂度降为 $O(n\log (n))$ 。

总时间复杂度为 $O(n^3+qn\log (n))$ 。

参考代码

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

const int MAXN=330;
const int mod=1e9+7;
const int inf=1<<30;
int pw[MAXN][MAXN+1000];
int inv[MAXN],a[MAXN],h[MAXN],d[MAXN];
int A[MAXN][MAXN],v[MAXN][MAXN],sum[MAXN][MAXN],c[MAXN][MAXN];
int n;

int add(int a,int b)
{
	return a+b>=mod?a+b-mod:a+b;
}

int dec(int a,int b)
{
	return a-b<0?a-b+mod:a-b;
}

int mul(int a,int b)
{
	return 1ll*a*b%mod;
}

int MOD(int x)
{
	x%=mod;
	if(x<0)
		x+=mod;
	return x;
}

void addBIT(int *t,int x,int d)
{
	while(x<=n)
	{
		t[x]=add(t[x],d);
		x+=x&(-x);
	}
}

int query(int *t,int x)
{
	int ret=0;
	while(x)
	{
		ret=add(ret,t[x]);
		x-=x&(-x);
	}
	return ret;
}

void build()
{
	memset(sum,0,sizeof(sum));
	int i,j;
	for(i=n;i>=1;i--)
	{
		//求 d[i] 
		if(a[i]>0)
			d[i]=0;
		else
			d[i]=inf;
		for(j=i+1;j<=n;j++)
		{
			if(A[i][j])
				d[i]=min(d[i],d[j]+1);
		}
		//先单点记录修改 
		if(d[i]!=inf)
		{
			for(j=1;j<=i;j++)
			{
				if(c[i][j])
					sum[j][d[i]+1]=add(sum[j][d[i]+1],
						mul(mul(pw[j][n-d[i]],c[i][j]),MOD(a[i])));
			}
		}
	}
	//汇总到树状数组上 
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			sum[i][j]=add(sum[i][j-1],sum[i][j]);
		for(j=n;j>=1;j--)
			sum[i][j]=dec(sum[i][j],sum[i][j^(j&(-j))]);
	}
}

int main()
{
	int i,j,k,sz,q,op,l,r,id,x,t,tmp,ans;
	scanf("%d",&n);
	inv[0]=inv[1]=1;
	//O(N)求逆元 
	for(i=2;i<=n;i++)
		inv[i]=mul(mod-mod/i,inv[mod%i]);
	//打指数表 
	for(i=1;i<=n;i++)
	{
		pw[i][n]=1;
		for(j=n-1;j>=0;j--)
			pw[i][j]=mul(pw[i][j+1],inv[i]);
		for(j=n+1;j<=n+1000;j++)
			pw[i][j]=mul(pw[i][j-1],i);
	}
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	//构造矩阵 A 
	for(i=1;i<=n;i++)
	{
		scanf("%d",&sz);
		A[i][i]=i;
		while(sz--)
		{
			scanf("%d",&j);
			A[i][j]=j;
		}
	}
	//求特征向量 
	for(i=1;i<=n;i++)
	{
		v[i][i]=1;
		for(j=i-1;j>=1;j--)
		{
			t=dec(i,j);
			tmp=0;
			for(k=j+1;k<=i;k++)
				tmp=add(tmp,mul(v[i][k],A[j][k]));
			v[i][j]=mul(tmp,inv[t]);
		}
	}
	//拆分单位向量 
	for(i=1;i<=n;i++)
	{
		h[i]=1;
		for(j=i;j>=1;j--)
		{
			if(h[j])
			{
				c[i][j]=h[j];
				t=h[j];
				for(k=1;k<=j;k++)
					h[k]=dec(h[k],mul(t,v[j][k]));
			}
		}
	}
	//特征向量前缀和处理
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			v[i][j]=add(v[i][j-1],v[i][j]);
	build();
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d",&x,&l,&r);
			ans=0;
			for(i=1;i<=n;i++)
			{
				tmp=query(sum[i],min(x+1,n));
				ans=add(ans,mul(mul(tmp,pw[i][x+n]),dec(v[i][r],v[i][l-1])));
			}
			for(i=l;i<=r;i++)
			{
				if(d[i]>x)
					ans=add(ans,MOD(a[i]));
			}
			printf("%d\n",ans); 
		}
		else
		{
			scanf("%d%d",&id,&x);
			if(a[id]<=0&&a[id]+x>0)
			{
				a[id]+=x;
				build();
			}
			else
			{
				a[id]+=x;
				if(d[id]!=inf)
				{
					for(i=1;i<=id;i++)
					{
						if(c[id][i])
							addBIT(sum[i],d[id]+1,mul(mul(c[id][i],x),pw[i][n-d[id]]));
					}
				}
			}
		}
	}
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198