codeforces 380D. Sereja and Cinema（#223div1 組合數學）

題目連結：【D. Sereja and Cinema】

電影院有n個位置，每個位置兩邊都有一個放東西的地方，當一個人進來之後他會立即占有位置兩邊空着的儲物格，要是他到的時候，座位的兩邊的儲物格都已經被占有了，那這個人就會離開

輸入n（1<=n<=10^5）個數，第i個數是c（1<=c<=n），表示第i個座位上的人是第c個進入影院的，如果c=0，表示這個位置上的人進入的順序未知，求能夠使得最終一個人都不離開影院的方案數

樣例：

6

0 1 0 0 0 6

有一種情況絕對會有一個人會離開，a，b，c位置相鄰，對應的進入順序是ai，bi，ci，如果bi比ai，ci都大，那麼bi肯定占不到儲物格

按照這個思想，我們可以用pair<>來記錄進入順序和位置，first記錄的是進入順序，second記錄的是位置，排序，維護一個區間[l, r]，

如果第一個進入的人位置是确定的，那麼第二個人進入的人的位置一定在第一個人的旁邊，也就是說後一個進入的位置一定在前一個進入的位置區間的兩側

看樣例，第一個進入的是位置2，此時位置區間是[2,2]，第六個位置時第六個進入的，第二個位置與第六個位置之間有3個位置，第1個進入與第六個進入的人之間還有4個人要進入，是以第一個與第六個之間的進入順序可以有C（4,3）個，之後位置區間就擴充到[1,6]

如果第一個人進入的位置不确定，那就枚舉第一個進入的位置

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define ll __int64
const int inf = 1e5+10;
const int mod = 1e9+7;
pair<int, int>a[inf];
int n, x, tot;
ll ans, ai[inf], bi[inf];
ll mul(ll x, int num)
{
	ll e = 1;
	while(num)
	{
		if(num&1) e = (x*e)%mod;
		x = (x*x)%mod;
		num>>=1;
	}
	return e; 
}
ll C(int ni, int mi)
{
	return ai[ni]*bi[mi]%mod*bi[ni-mi]%mod;
}
void find(int x, int y)
{
	int l = y, r = y;
	ll sum = 1;
	for(int i=x; i<=tot; i++)
	{
		int num=a[i].first-a[i-1].first-1;
		int dis=a[i].second;
		if(l<=dis && dis<=r) return;
		if(dis < l)
		{
			if(l-dis-1 > num) return;
			int tmp1=l-dis-1, tmp2=num-tmp1;
			l = dis;
			r = r+tmp2;
			sum = sum*C(num, tmp1)%mod;
		}
		else
		{
			if(dis-r-1 >num) return;
			int tmp1=dis-r-1, tmp2=num-tmp1;
			l = l-tmp2;
			r = dis;
			sum = sum*C(num, tmp1)%mod;
		}
	}
	ans = (ans+sum)%mod;
}
int main()
{
	tot=0;
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d", &x);
		if(x)
		{
			a[++tot].first = x;
			a[tot].second = i;	
		}
	}
	a[++tot].first = n+1;
	a[tot].second = n+1;
	ai[0]=1, bi[0]=1;
	for(int i=1; i<=n; i++) ai[i]=ai[i-1]*i%mod;
	for(int i=1; i<=n; i++) bi[i]=mul(ai[i], mod-2);
	sort(a+1, a+tot+1);
	ans = 0;
	a[0].first = 1;
	if(a[1].first == 1) find(2, a[1].second);
	else
	{
		for(int i=1; i<=n; i++)
		{
			find(1, i);
		}
	}
	printf("%I64d\n", ans);
	return 0;
}