CF1204

Posted on | Views:

$Div.2$

A BowWow and the Timetable

判断一下读入的数是不是 $0$ 或者 $4$ 的幂次.

B Mislove Has Lost an Array

若首先放入 $1,2,4,\dots 2^{l-1}$ ,剩下的位置都放入 $1$ ,得到的和最小.

若首先放入 $1,2,4,\dots,2^{r-1}$ ,剩下的位置都放入 $2^{r-1}$ ,得到的和最大.

C Anna, Svyatoslav and Maps

如果上个点到下个点的所有最短路都不经过当前点,那么当前点必须选.

$floyd$ 预处理两点间最短路长度后进行判断.

D Kirk and a Binary String

将原串中的 $10$ 子串全部删去,再把剩余的 $1$ 改成 $0$ ,将删掉的 $10$ 放回原位即得答案.

因为这样的子串对 $LIS$ 的贡献只可能是 $1$ ,所以删掉不会造成影响.

E Natasha, Sasha and the Prefix Sums

记 $sum$ 表示 $a$ 的前缀和.

考虑枚举 $x=f(a)$ ,并且枚举第一次得到这个前缀和时,用了 $y$ 个 $1$ .

即,若 $k$ 是第一个使得 $sum(k)=x$ 的位置,从 $1$ 到 $k$ 一共有 $y$ 个 $1$ ,那么从 $1$ 到 $k$ 一共有 $y-x$ 个 $-1$ .

求出这种数列的方案数 $t$ ,那么这些数列对答案的贡献就是 $t\cdot x$ .

由于位置 $k$ 一定是 $1$ ,所以只需要分别求出 $1\sim k-1$ 与 $k+1\sim n+m$ 这两段的方案数,相乘即为 $t$ .

$1\sim k-1$ 的 $1,-1$ 的个数都是确定的,只要求每个位置从 $1$ 开始的前缀和都 $<x$ .

$k+1\sim n+m$ 的 $1,-1$ 个数也是确定的,只要求每个位置从 $k+1$ 开始前缀和都 $\le 0$ .

这两个问题都可以归纳为在二维平面上,从 $(0,0)$ 走到 $(X,Y)$ ,每次只能往右或上走一格,并且不能触碰到直线 $y=x+b$ 的方案数,注意不能跨越也可以转化为不能触碰,将直线向上平移一个位置即可.

设原点关于该直线的对称点为 $P$ ,答案就是从原点走到终点的方案数减去从 $P$ 走到终点的方案数,都不考虑限制.

因为从 $P$ 走到终点的每种方案都恰好对应了一种从原点走到终点,但触碰到了直线的方案.

时间复杂度 $O(n^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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=4e3+10;
const int P=998244853;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int inv(int x)
{
	return fpow(x,P-2);
}
int fac[MAXN],invfac[MAXN];
void Init(int N)
{
	fac[0]=invfac[0]=1;
	for(int i=1;i<=N;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[N]=inv(fac[N]);
	for(int i=N-1;i>=1;--i)
		invfac[i]=mul(invfac[i+1],i+1);
}
int C(int M,int N)
{
	if(N>M || N<0 || M<0)
		return 0;
	return mul(fac[M],mul(invfac[N],invfac[M-N]));
}
int ans=0,n,m;
int calc(int x,int y,int b)//(0,0)->(x,y),without touching y=x+b
{
	return add(C(x+y,y),P-C(x+y,y-b));
}
int main()
{
	Init(4000);
	n=read(),m=read();
	for(int x=1;x<=n;++x)
		for(int y=x;y<=n && y-x<=m;++y)
		{
			int t=calc(y-x,y-1,x);
			t=mul(tmp,calc(m+x-y,n-y,1));
			ans=add(ans,mul(tmp,x));
		}
	cout<<ans<<endl;
	return 0;
}