网站模板上传教程视频教程,湖北网站建设,网站备案取名,福州专业做网站problem
洛谷链接
solution
一个 AiA_iAi 只会影响一个 BiB_iBi#xff0c;BiB_iBi 之间的决定因素 AAA 是不会有交的。
所以如果相邻两个对同一个 BiB_iBi 影响的 A2i,A2i−1A_{2i},A_{2i-1}A2i,A2i−1 都是确定的#xff0c;那么 BiB_iBi 也就确定了。
…problem
洛谷链接
solution
一个 AiA_iAi 只会影响一个 BiB_iBiBiB_iBi 之间的决定因素 AAA 是不会有交的。
所以如果相邻两个对同一个 BiB_iBi 影响的 A2i,A2i−1A_{2i},A_{2i-1}A2i,A2i−1 都是确定的那么 BiB_iBi 也就确定了。
这是不会对方案数产生贡献的提前预处理掉这些位置接下来的计算不考虑这些出现的值。
同时如果都不确定这些配对位置的值可以互换即原本 −1-1−1 的位置是无序的所以最后的答案要乘上一个阶乘。
BiB_iBi 是取较小值容易想到从大到小考虑填的数那么BiB_iBi 就仅由 A2i,A2i−1A_{2i},A_{2i-1}A2i,A2i−1 后填的数决定。
下面将 A2i−1,A2iA_{2i-1},A_{2i}A2i−1,A2i 没全填的称为“未配对”。
设 f(i,j,k):f(i,j,k):f(i,j,k): 已考虑到数第 iii 大时有 jjj 个明确指定的数还未配对有 kkk 个原本未知 −1-1−1 然后填了个数也还未配对 的方案数。
考虑由 f(i,j,k)f(i,j,k)f(i,j,k) 转移到 i1i1i1即 Ai1A_{i1}Ai1 的配对情况。 如果 Ai1A_{i1}Ai1 原本是指定的数Ai1≠−1A_{i1}\neq -1Ai1−1。 可以和未知数配对f(i,j,k)→f(i1,j,k−1)f(i,j,k)\rightarrow f(i1,j,k-1)f(i,j,k)→f(i1,j,k−1)。可以新增一个已知数的未配对f(i,j,k)→f(i,j1,k)f(i,j,k)\rightarrow f(i,j1,k)f(i,j,k)→f(i,j1,k)。 如果 Ai1−1A_{i1}-1Ai1−1未知。 可以新增一个未知数的未配对f(i,j,k)→f(i,j,k1)f(i,j,k)\rightarrow f(i,j,k1)f(i,j,k)→f(i,j,k1)。 可以和未知数配对f(i,j,k)→f(i1,j,k−1)f(i,j,k)\rightarrow f(i1,j,k-1)f(i,j,k)→f(i1,j,k−1)。 可以和已知数配对f(i,j,k)×j→f(i1,j−1,k)f(i,j,k)\times j\rightarrow f(i1,j-1,k)f(i,j,k)×j→f(i1,j−1,k)。 因为已知数的位置是固定的所以 Ai1A_{i1}Ai1 和 jjj 个已知数配对都是不同的情况。 而和未知数的配对是不考虑 ×k\times k×k 的。本来位置就不固定在最后的阶乘时候已经算入了这里再乘就算重了。
初始状态 f(0,0,0)1f(0,0,0)1f(0,0,0)1。
code
#include bits/stdc.h
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 605
int n, m, cnt, fac;
int a[maxn], c[maxn], g[maxn];
int f[maxn][maxn][maxn];signed main() {scanf( %lld, n ), n 1;for( int i 1;i n;i ) scanf( %lld, a[i] );for( int i 1;i n;i 2 ) {if( a[i] -1 and a[i 1] -1 ) cnt ;else if( ~ a[i] and ~ a[i 1] ) g[a[i]] g[a[i 1]] 2;else {if( ~ a[i] ) g[a[i]] 1;else g[a[i 1]] 1;}}for( fac 1;cnt;fac fac * cnt % mod, cnt -- );for( int i n;i;i -- ) if( g[i] ^ 2 ) c[ m] i;f[0][0][0] 1;for( int i 0;i m;i )for( int j 0;j n;j )for( int k 0;k n;k )if( ! f[i][j][k] ) continue;else if( g[c[i 1]] ) { //已知数( f[i 1][j 1][k] f[i][j][k] ) % mod; //新增一个未匹配的已知数if( k ) ( f[i 1][j][k - 1] f[i][j][k] ) % mod; //和未知数匹配}else { //未知数( f[i 1][j][k 1] f[i][j][k] ) % mod; //新增一个未匹配的未知数if( j ) ( f[i 1][j - 1][k] f[i][j][k] * j % mod ) % mod; //和已知数配对if( k ) ( f[i 1][j][k - 1] f[i][j][k] ) % mod; //和未知数匹配}printf( %lld\n, f[m][0][0] * fac % mod );return 0;
}
