莫队维护离线杨辉三角按行求和：ABC463 G

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162421138

https://atcoder.jp/contests/abc463/tasks/abc463_g

前面的式子处理是容易的，令 m=n−x,k=⌊m2⌋m=n-x,k=\lfloor \frac{m}{2}\rfloor ，即求：

12n(m(∑i=0k(ni)−∑i=k+1n(ni))+2(∑i=0k(ni)(−i)+∑i=k+1n(ni)i))\frac{1}{2^n}\left(m\left(\sum_{i=0}^k\binom{n}{i}-\sum_{i=k+1}^n\binom{n}{i}\right)+2\left(\sum_{i=0}^k\binom n i(-i)+\sum_{i=k+1}^n\binom n i i\right)\right)

令 f(n,k)=∑i=ik(ni)f(n,k)=\sum_{i=i}^k\binom n i , g(n,k)=∑i=1k(ni)ig(n,k)=\sum_{i=1}^k\binom n i i

显然有 g(n,k)=n×f(n−1,k−1)g(n,k)=n\times f(n-1,k-1)

现在考虑怎么求 f(n,k)f(n,k)

这是一个 杨辉三角按行求和的套路 ，首先有：

f(n,k+1)=f(n,k)+(nk+1)f(n+1,k)=2f(n,k)−(nk)f(n,k+1)=f(n,k)+\binom n {k+1}\\[10pt] f(n+1,k)=2f(n,k)-\binom n k

因为我们要询问多个 f(n,k)f(n,k) ，所以我们可以 离线后用莫队维护

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 200010
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) {
	return pw(a, mo - 2); 
}
void Mod(int &a) {
	a = (a % mo + mo) % mo; 
}
void Add(int &a, int b) {
	a += b; Mod(a); 
}
#define Lim 200000
int n, m, i, j, k, T;
int fac[N], ifac[N], inv[N], tw[N], su[N], itw[N]; 
map<pair<int, int>, int>mp; 
vector<pair<int, int> >v; 
int L, R, l, r, cnt, sq, iv2, x, ans; 
int an[N], am[N], ax[N], ak[N]; 

void init(int n) {
	sq = sqrt(n); iv2 = pw(2); 
	for(i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mo; 
	for(i = tw[0] = 1; i <= n; ++i) tw[i] = tw[i - 1] * 2 % mo; 
	ifac[n] = pw(fac[n]); itw[n] = pw(tw[n]); 
	for(i = n; i >= 1; --i) ifac[i - 1] = ifac[i] * i % mo; 
	for(i = n; i >= 1; --i) itw[i - 1] = itw[i] * 2 % mo; 
	for(i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i - 1] % mo; 
	for(i = 0; i <= n; ++i) su[i] = i / sq;
}

//int f(int n, int k) {
//	auto C = [&] (int n, int m) -> int {
//		if(m < 0 || m > n) return 0;  
//		return fac[n] * ifac[m] % mo * ifac[n - m] % mo; 
//	}; 
//	int ans = 0; 
//	for(int i = 0; i <= k; ++i) Add(ans, C(n, i)); 
//	return ans; 
//}

int f(int x, int y) {
	return mp[{x, y}]; 
}

int g(int n, int k) {
	if(k == 0) return 0; 
	return n * f(n - 1, k - 1); 
}


//
//int g(int x, int y) {
//	if(y == 0) return 0; 
//	return x * f(x - 1, y - 1); 
//}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	init(Lim); 
	auto C = [&] (int n, int m) -> int {
		if(m < 0 || m > n) return 0;  
		return fac[n] * ifac[m] % mo * ifac[n - m] % mo; 
	}; 
	for(int t = 1; t <= T; ++t) {
		n = an[t] = read(); 
		x = ax[t] = read(); 
		m = am[t] = - (x - n); 
		k = ak[t] = m / 2; 
		if(x <= -n || x >= n) continue; 
		v.pb({n, k}); 
		v.pb({n - 1, n - 1}); 
		if(k) v.pb({n - 1, k - 1}); 
	}
	auto cmp = [&] (pair<int, int> x, pair<int, int> y) -> bool {
		if(su[x.fi] == su[y.fi]) return x.se > y.se; 
		return su[x.fi] > su[y.fi]; 
	}; 
	sort(v.begin(), v.end(), cmp); 

	L = 1, R = 0; cnt = 1; 
	for(auto t : v) {
		L = t.fi; R = t.se; 
		while(r < R) Add(cnt, C(l, r + 1)), ++r; 
		while(r > R) Add(cnt, -C(l, r)), --r; 
		while(l < L) cnt = 2 * cnt - C(l, r), Mod(cnt), ++l; 
		while(l > L) cnt = (cnt + C(l - 1, r)) * iv2, Mod(cnt), --l; 
		mp[{l, r}] = cnt; 
	}
	for(int t = 1; t <= T; ++t) {
		n = an[t]; k = ak[t]; m = am[t]; x = ax[t]; 
		if(x <= -n || x >= n) {
			printf("%lld\n", abs(x)); 
			continue; 
		}
		ans = m * (2 * f(n, k) - tw[n]) + 2 * (g(n, n) - 2 * g(n, k)); 
		Mod(ans); ans = ans * itw[n]; Mod(ans); 
		printf("%lld\n", ans);  
	}
	for(int t = 1; t <= T; ++t) {
		n = an[t]; k = ak[t]; m = am[t]; x = ax[t]; 
		if(x <= -n || x >= n) {
//			printf("%lld\n", abs(x)); 
			continue; 
		}
//		int X = f(n + 1, k), Y = 2 * f(n, k) - C(n, k); 
//		Mod(X); Mod(Y); 
//		printf(X == Y ? "True\n" : "False\n"); 
	}
	return 0;
}