https://codeforces.com/contest/1622/problem/D

대회중에 포함배제로 접근해서 왜 되는지 모르겠고 깊이 1까지만 처리하니까 예제나와서 제출했더니 맞음. 구간에서 포함배제하면 구간에 0부터 번호매겨서 a[i]로 부르자.

a[0]은 a[0<i<k] 와 k-1개, k-2개, ... 1개 겹치는 경우를 빼줘야하고 이는 Choose(len,k-1)이 되서 깊이 1만 처리해도 맞았던거다.
a[1]은 a[1<i<k+1] 과 k-1개, ..., 1개 겹치는 경우 빼줘야 하고 이는 위와 같음.
a[n-?] 끝부분은 어떻게 된거지? 

#######
 #######
  #######
	 #######
	  #######
		 #######
위의 길이7짜리 나이브 계산결과는 7개짜리 움직임, 6개짜리 움직임*2, 5개짜리 움직임*3.. 형태임

######
 ######
  ######
	 ######
	  ######
이 6짜리는 6개짜리 움직임, 5개짜리 움직임*2, ... 형태임.

따라서 둘을 빼주면 7개의 움직임, 6개의 움직임, 5개의 움직임 ... 이렇게 되서 중복이 없어진다.

뭔소리냐면
맨앞 구간에서 길이6짜리는 다음구간 하나와 겹침=2번 세짐
맨앞구간 길이5짜리 뒤쪽에 붙어있는거는 다음꺼와 다음다음꺼에도 포함되있음 = 3번 세짐
단, 맨앞구간 길이5짜리 뒤쪽에서 한칸 떨어진거는 다음꺼에만 세짐 = 2번 세짐. 근데 그것도 뺄때 길이6짜리 첫구간에서만 빠지니까(=빼기1) 한번만 세게 됨.
그니까 6짜리는 기본적으로 2번세지는데 맨앞에 1번 세지는게 있긴 하지만 빼는것도 하나 줄어든 0개 빼게 되므로 괜찮음
5짜리도 맨앞꺼는 1번세고 0번뺌, 앞에서 두번째는 2번세고 1번뺌, 이외에는 기본적으로 3번세고 2번뺌.
이런식으로 된다는거.

구간 포함배제 테크닉이라고 부를 수 있으려나?