广州做网站开发,广州市律师网站建设怎么样,参考网是正规网站吗,用户体验设计要素题目大意
有n个数#xff0c;让你对其排列#xff0c;令排列后的第i个数字为sis_isi#xff0c;该排列要满足#xff1a; ∀i∈[1,n),si≤si1\forall i\in [1,n),s_i\leq s_{i1}∀i∈[1,n),si≤si1∀i∈[1,n),∣(min(si,si1),max(si,si1))∩{sj∣ki}∣≤bi\fora…题目大意
有n个数让你对其排列令排列后的第i个数字为sis_isi该排列要满足
∀i∈[1,n),si≤si1\forall i\in [1,n),s_i\leq s_{i1}∀i∈[1,n),si≤si1∀i∈[1,n),∣(min(si,si1),max(si,si1))∩{sj∣ki}∣≤bi\forall i\in [1,n),\begin{vmatrix}(min(s_i,s_{i1}),max(s_i,s_{i1}))\cap \{s_j| ki\}\end{vmatrix}\leq b_i∀i∈[1,n),∣∣(min(si,si1),max(si,si1))∩{sj∣ki}∣∣≤bi
输出方案数 解题思路
设fs,if_{s,i}fs,i为状态为s最后一个数为i的方案数
那么每次选择一个可行的点转移最后取所有点都排列好的状态即可 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 20
#define M 263000
#define wyc 4921057
using namespace std;
int n,num,now,ans,a[N],b[N],v[N],f[M][N];
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);v[a[i]];}for(int i1;in;i)scanf(%d,b[i]);for(int i2;i10;i)v[i]v[i-1];for(int i1;in;i)if(!v[a[i]-1])f[1i-1][i]1;for(int s1;s(1n)-1;s){num0;for(int i1;in;i)if(s(1i-1))num;for(int i1;in;i)if(s(1i-1)f[s][i]){now0;for(int ji1;jnnowb[i];j)if(!(s(1j-1))){if(a[j]a[i]||a[j]a[i]numv[a[i]])(f[s|(1j-1)][j]f[s][i])%wyc;now;}now0;for(int ji-1;j0nowb[i];--j)if(!(s(1j-1))){if(a[j]a[i]||a[j]a[i]numv[a[i]])(f[s|(1j-1)][j]f[s][i])%wyc;now;}}}for(int i1;in;i)(ansf[(1n)-1][i])%wyc;;printf(%d,ans);return 0;
}
