牛客手速月赛61 F(又是被20级打爆的一天)

题目
题意: 放映厅中有n张椅子，f(x)表示有x位观影者的方案数，要求观影者是连续坐的。并且有m条限制，必须同时满足才行。第i条的限制是，ai或bi或ci中至少有一个被观影者坐了。
思路: 考虑到[l,r+1]不会比[l,r]更差，只会不变或者更优。所以我们对于每个l，都可以找到对应的最小的r，长度为r-l+1到n-l+1的方案数+1，这个用差分维护即可。最后求和完记得乘以x的阶乘，因为他们内部可以任意组合。
代码:

#include
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9+7;
int n,m,k,T;
vector<int> va[N];
int b[N];
int cnt[N];
int now;
void add(int x)
{
	for(int i=0;i<va[x].size();++i)
	{
		int j = va[x][i];
		if(++cnt[j]==1)
		{
			now++;
		}
	}
}
void del(int x)
{
	for(int i=0;i<va[x].size();++i)
	{
		int j = va[x][i];
		if(--cnt[j]==0)
		{
			now--;
		}
	}
}
void solve()
{
	cin>>n>>m;
	for(int t=0;t<3;++t)
	for(int i=1;i<=m;++i)
	{
		int x; cin>>x;
		va[x].push_back(i);
	}
	for(int l=1,r=0;l<=n;l++)
	{
		while(r+1<=n&&now<m) add(++r);
// 		cout<
		if(now==m)
		{
			b[r-l+1]++;
			b[n-l+2]--;
		}
		else break;
		del(l);
	}
	ll fac = 1;
	for(int i=1;i<=n;++i)
	{
		fac = fac * i % mod; 
		b[i] = (b[i]+b[i-1]) % mod;
		cout<<1ll*b[i]*fac%mod<<" ";
	}
}
signed main(void)
{
	solve();
	return 0;
}
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