A
据说是抄重了。。
B
首先肯定二分答案，设二分的答案为 $x$，最终的权值是 $B$，设一对相邻的点为 $(i,j),(k,l)$，那么一定要满足 $|B_{i,j}-B_{k,l}| \leq x$。可以把绝对值拆开，于是就是 $B_{i,j}-B_{k,l} \leq x$，也就是 $B_{k,l} \geq B_{i,j}-x$（因为这个题要增加，所以我们就搞出下界）
显然的贪心是让每个点增加到下界即可。这个形式可以跑一个类似差分约束的东西：每次取出最大值去更新周围的点即可。
如果点对 $(i,j)$ 贡献到了 $(k,l)$，一定是以 $A_{i,j}-xdis((i,j),(k,l))$ 的值更新的，所以我们一定是沿着最短路更新。我们发现在六边形图中最短路只会拐一次弯（六边形图中每种向量都可以由不超过两个基向量合成），所以我们先让编号小的更新编号大的，再让编号大的更新编号小的，再让编号小的更新编号大的就行了。复杂度 $O(n \log V)$。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e5 + 5;
std::vector<std::vector<LL> > G,GG;
int n,m;
LL k;
const int dx[] = {0,1,1,0,-1,-1};
const int dy[] = {-1,-1,0,1,1,0};
int main(){
scanf("%d%d%lld",&n,&m,&k);
G = std::vector<std::vector<LL> >(n+3,std::vector<LL>(m+3,0));
FOR(i,1,n) FOR(j,1,m) scanf("%lld",&G[i][j]);
LL l = 0,r = 1e12,ans = -1;
while(l <= r){
LL mid = (l + r) >> 1;
auto chk = [&](){
GG = G;
FOR(x,1,n){
ROF(y,m,1){
FOR(k,0,2){
int xx = x+dx[k],yy = y+dy[k];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m) GG[xx][yy] = std::max(GG[xx][yy],GG[x][y]-mid);
}
}
}
ROF(x,n,1){
FOR(y,1,m){
FOR(k,3,5){
int xx = x+dx[k],yy = y+dy[k];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m) GG[xx][yy] = std::max(GG[xx][yy],GG[x][y]-mid);
}
}
}
FOR(x,1,n){
ROF(y,m,1){
FOR(k,0,2){
int xx = x+dx[k],yy = y+dy[k];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m) GG[xx][yy] = std::max(GG[xx][yy],GG[x][y]-mid);
}
}
}
LL ans = 0;
FOR(i,1,n) FOR(j,1,m) ans += GG[i][j]-G[i][j];
return ans <= k;
};
if(chk()) ans = mid,r = mid-1;
else l = mid+1;
}
printf("%lld\n",ans);
return 0;
}
C
人傻了，这个题直接数位 dp 就行。
首先我们发现我们可以按照 $1$ 个数分类，我们把询问拆成前 $a$ 大的和，答案一定是包含若干个连续段和一个段的某个部分，一个段的某个部分的询问形如询问 $1$ 的个数为 $x$，前 $y$ 大的和。
这种题目我们都考虑从高到低按位确定，先预处理 $f_{i,j,0/1,0/1}$ 表示从高到低考虑了前 $i$ 位，选了 $j$ 个 $1$，是否卡上下界的方案数，$g_{i,j,0/1,0/1}$ 记录所有方案的和，转移的时候枚举这一位填什么就行了。
我们在处理询问「求 $1$ 的个数为 $x$ ，前 $y$ 大的和」的时候可以递归处理：设一个函数 $dp(i,j,0/1,0/1,k)$ 表示从高到低考虑前 $i$ 位，选了 $j$ 个 $1$，是否卡上界，要求前 $k$ 大的方案数和方案的和。如果当前有 $f_{i,j,0/1,0/1 }\leq k$ 就直接返回 $g$ ，否则我们先让这一位填 $1$ 算算方案数，再减掉去算这一位填 $0$ 的。
代码实现是转化为求前 $i$ 小了，本质是相同的。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<LL,LL>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXM = 29;
P f[31][31][2][2];
int L,R;
inline void Solve(){
auto add = [&](const P &a,const P &b){
return MP(a.fi+b.fi,a.se+b.se);
};
// 前 i 个 选了 j 个 1 上下界 要求<=k
std::function<P(int,int,int,int,int,bool)> dp = [&](int i,int j,int l,int r,int k,bool fg){
if(j < 0 || !k || i < 0) return MP(0ll,0ll);
if(fg && f[i][j][l][r].fi <= k) return f[i][j][l][r];
int u = (!r)|((R>>i)&1),d = l&((L>>i)&1);
P t0 = d==0?dp(i-1,j,l&(!((L>>i)&1)),r&(!((R>>i)&1)),k,1):MP(0ll,0ll);
P t1 = u==1?dp(i-1,j-1,l&((L>>i)&1),r&((R>>i)&1),k-t0.fi,1):MP(0ll,0ll);
if(i == 1 && j == 2 && l == 1 && r == 0){
}
return MP(t0.fi+t1.fi,t0.se+t1.se+t1.fi*(1ll<<i));
};
auto work = [&](int lim){
LL ans = 0;
FOR(i,0,MAXM){
P t = f[MAXM][i][1][1];
if(lim >= t.fi){
lim -= t.fi;
ans += t.se;
continue;
}
ans += dp(MAXM,i,1,1,lim,0).se;
break;
}
return ans;
};
CLR(f,0);int a,b;
scanf("%d%d%d%d",&L,&R,&a,&b);
a = R-L+1-a+1;b = R-L+1-b+1;
std::swap(a,b);
f[0][0][0][0] = f[0][0][0][1] = MP(1,0);
f[0][0][1][0] = f[0][0][1][1] = MP(!(L&1),0);
f[0][1][0][0] = f[0][1][1][0] = MP(1,1);
f[0][1][0][1] = f[0][1][1][1] = MP(R&1,R&1);
FOR(i,1,MAXM) FOR(j,0,i+1) FOR(l,0,1) FOR(r,0,1) f[i][j][l][r] = dp(i,j,l,r,1e9,0);
printf("%lld\n",work(b)-work(a-1));
}
int main(){
int T;scanf("%d",&T);
while(T--) Solve();
return 0;
}D
每种方案对答案的贡献是「有序选出两个不同的位置，值相同的方案数」加上 $1$。因为 $x^2 = 1+2\binom x 2$。
所以一个 $n^3$ 的做法就是我们先枚举计算每个数 $x$ 的贡献，然后 $f_{i,j,k}$ 表示考虑了前 $i$ 个数， 当前最大值为 $j$ ，选了 $k$ 个 $x$ 的方案数，转移分类讨论：
- $f_{i,j,k} \gets f_{i-1,j,k}\times j$
- $f_{i,j,k} \gets f_{i-1,j-1,k}$
- 如果 $j=x$，那么 $f_{i,j,k} \gets f_{i-1,j-1,k-1}$
- 如果 $j \geq x$，那么 $f_{i,j,k} \gets f_{i-1,j,k-1}$
优化和这个 dp 没啥关系。。一个直观的想法是去枚举 $x$ 第一次出现的位置 $i$，我们设 $f_{i,j}$ 表示前 $i$ 个数，最大值为 $j$ 的方案数（不难发现这个是第二类斯特林数），设 $g_{i,j}$ 表示在最大值为 $j$ 的序列拼上长度为 $i$ 的序列的方案数。
那么对于一个在位置 $i$ 的数字 $x$，方案数就是：
$$ f_{i-1,x-1}(g_{n-i,x}+2(n-i)g_{n-i-1,x}) + \sum_{y \geq x} f_{i-1,y}(g_{n-i,y}+2(n-i)g_{n-i-1,y}) $$
（后面的 $2(n-1)$ 是从 $n-i$ 个位置选出另一个 $x$，让这两个配对，这种方式贡献的系数为 $2$）
预处理后缀和即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 3000+5;
int n,ha;
int main(){
auto add = [&](int &x,int y){
x += y-ha;x += x>>31&ha;
};
scanf("%d%d",&n,&ha);
static int f[MAXN][MAXN],g[MAXN][MAXN];f[0][0] = 1;
FOR(i,1,n) FOR(j,1,n) f[i][j] = (1ll*f[i-1][j]*j%ha+f[i-1][j-1])%ha;
FOR(i,1,n) g[0][i] = 1;
// max=j 后拼长度为 i 的序列
// g[i][j] = g[i-1][j]*j + g[i-1][j+1]
FOR(i,1,n) FOR(j,1,n) g[i][j] = (1ll*g[i-1][j]*j%ha+g[i-1][j+1])%ha;
static int sm[MAXN][MAXN];
FOR(i,1,n){
ROF(j,n,1){
sm[i][j] = 1ll*f[i-1][j]*(g[n-i][j]+2ll*(n-i)%ha*g[n-i-1][j]%ha)%ha;
// if(i == 3)DEBUG(sm[i][j]);
add(sm[i][j],sm[i][j+1]);
}
}
FOR(x,1,n){
int ans = 0;
FOR(i,1,n){ // 枚举第一个 x 所在的位置
int gx = sm[i][x];
add(gx,1ll*f[i-1][x-1]*(g[n-i][x]+2ll*(n-i)%ha*g[n-i-1][x]%ha)%ha);
add(ans,gx);
}
printf("%d%c",ans," \n"[x==n]);
}
return 0;
}