>Link

luogu U137979

---

>Description

对于 100% 的数据， 1 ≤ b i ≤ n ≤ 18 , 1 ≤ a i ≤ 10 1 ≤b_i ≤ n ≤ 18, 1 ≤ a_i ≤ 10 1≤bi​≤n≤18,1≤ai​≤10

---

>解题思路

一开始没看数据范围想了好久QAQ

然后一看这个数据范围应该就是状压DP
设 f s , i f_{s,i} fs,i​为在 s s s状态下，最后一个写的作业为第 i i i个的方案数，状态 s s s记录对应的作业有没有写
直接按照题意暴力判断当前枚举到的 s s s和 i i i是否合法
第二个条件我们发现是求当前 s s s状态下，某段区间的0的个数，可以预处理每个状态下0的前缀和，DP时 O ( 1 ) O(1) O(1)查询

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 25
using namespace std;

const int Mod = 4921057;
int n, a[N], b[N], sum[N], f[300000][N], T, minn, ans;
int tot[300000][N];

int main()
{
	int cnt, l, r; bool ok;
	minn = 10;
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)
	  scanf ("%d", &a[i]), sum[a[i]]++, minn = min (minn, a[i]);
	for (int i = 1; i <= n; i++) scanf ("%d", &b[i]);
	for (int i = 1; i <= 10; i++) sum[i] += sum[i - 1];
	
	T = (1 << n) - 1;
	for (int i = 1; i <= T; i++)
	  for (int j = 1; j <= n; j++)
	  {
	  	tot[i][j] = tot[i][j - 1];
	  	if (((i >> (j - 1)) & 1) == 0) tot[i][j]++;
	  }
	for (int i = 1; i <= n; i++)
	  if (a[i] == minn) f[1 << (i - 1)][i] = 1;
	for (int i = 1; i <= T; i++)
	  for (int j = 1; j <= n; j++)
	  {
	  	if (((i >> (j - 1)) & 1) == 0) continue;
	  	cnt = 0, ok = 1;
	  	for (int jj = 1; jj <= n; jj++)
	  	  if ((i >> (jj - 1)) & 1)
	  	  {
	  	  	if (a[jj] > a[j]) {ok = 0; break;}
	  	  	cnt++;
		  }
		if (!ok || cnt <= sum[a[j] - 1]) continue;
		int ii = i ^ (1 << (j - 1));
		for (int jj = 1; jj <= n; jj++)
		{
	  		if (((ii >> (jj - 1)) & 1) == 0) continue;
	  		/*cnt = 0;
	  		for (int t = min (j, jj) + 1; t < max (j, jj); t++)
	  		  if (((ii >> (t - 1)) & 1) == 0) cnt++;
	  		if (cnt <= b[jj]) f[i][j] = (f[i][j] + f[ii][jj]) % Mod;*/
	  		l = min (j, jj) + 1, r = max (j, jj) - 1;
	  		if (tot[ii][r] - tot[ii][l - 1] <= b[jj])
	  		  f[i][j] = (f[i][j] + f[ii][jj]) % Mod;
		}
	  }
	for (int i = 1; i <= n; i++)
	  ans = (ans + f[T][i]) % Mod;
	printf ("%d", ans);
	return 0;
}