T1[计数类DP/转化]给出2个排列p，q，长度都是n，其中p完全给出，\(\exists pi=0 \Leftrightarrow i位置可以填任意[1,n]之间的数使得q构成排列\)，问长度是n的01串S的个数，使得存在2*n的矩阵，满足\(a_{1,i}<a_{1,j}\Leftrightarrow pi<pj,a_{2,i}<a_{2,j}\Leftrightarrow qi<qj,si=0\Leftrightarrow a_{1,i}=a_{2,i}\)。(n<=100)
考场
没思路，发现枚举什么都会T飞，\(O(n!*2^n*n)\),然后发现对于qi=0的看起来就很随和，就蒙了一个\(2^n\),骗了5分
正解
套路性的思路转化，2个相对变化等价于只变化一个，所以sortp之后只需要考虑在a1升序下的满足条件，
偏序关系转化图论，发现1、2、3的条件使得矩形的任意上下点之间有边连接，定义\(ai>aj \Leftrightarrow edge(ai->aj)\),那么因为p顺序固定了，所以环（矛盾关系）方向固定了，所以矛盾当且仅当\(qi>qj,si=1,sj=0\).
抽象化s的含义，把10看成选或者不选，不合法序列就是\(\exists qi>qj,i和j都选择\),合法序列就是\(\forall i_{choose},j_{choose},qi<qj\),所以就是qi的上升子序列个数.
考虑没有空位只需要记录上一位最大，有就添加中间有多少已选择的未知，
\(f[i][j]:前i个数，ai是上升序列最后一位，有j个选择的qj=0的位置\)
\(f[i][j]+=f[k][l]*C(val[i-k],j-l)*C(chose[i-k],j-l)\),表示从k-i的区间中填补上l个上升子序列，可以选择的数值是在[qk,qi]之间没出现的，可以选择的位置是[k,i]之间0的个数。
\(ans=\sum f[n][l]*A(chose_n-l)\),表示剩下的空位随便选择，全排列。
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define chu printf
#define rint register int
#define ll long long
#define ull unsigned long long
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
const int N = 110;
const int mod = 998244353;
inline void upd(int& fg, int fp) {
fg += fp;
fg = (fg < 0) ? (fg + mod) : ((fg >= mod) ? (fg - mod) : fg);
}
int f[N][N], s[N], g[N], n, C[N][N];
int q[N], fac[N];
int chs[N];
struct node {
int a, b;
bool operator<(const node& U) const { return a < U.a; }
} p[N];
// f[i][j]:表示前i个数，有j个选择的不确定的位置的方案数
// s[i]:前i个位置有多少等着选择
// g[i]:前i个值有多少等着选择
int main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("surprise.in", "r", stdin);
freopen("surprise.out", "w", stdout);
n = re();
for (rint i = 1; i <= n; ++i) p[i].a = re();
for (rint i = 1; i <= n; ++i) p[i].b = re();
sort(p + 1, p + 1 + n);
for (rint i = 1; i <= n; ++i) q[i] = p[i].b;
chs[++chs[0]] = 0;
for (rint i = 1; i <= n; ++i) {
// chu("q[%d]:%d\n",i,q[i]);
if (q[i] == 0)
s[i] = s[i - 1] + 1;
else
s[i] = s[i - 1];
if (q[i])
g[q[i]] = 1, chs[++chs[0]] = i;
}
s[n + 1] = s[n];
q[n + 1] = n + 1;
chs[++chs[0]] = n + 1;
for (rint i = 1; i <= n; ++i) g[i] = g[i - 1] + (!g[i]); //有的值不选择
C[0][0] = 1;
for (rint i = 1; i <= n; ++i) {
// chu("q[%d]:%d\n",i,q[i]);
C[i][0] = 1;
for (rint j = 1; j <= i; ++j) upd(C[i][j], (1ll * (C[i - 1][j] + C[i - 1][j - 1]) % mod));
}
fac[0] = fac[1] = 1;
for (rint i = 2; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
f[0][0] = 1;
// chu("C[]:%d\n",C[5][2]);
for (rint I = 2, i = chs[I]; I <= chs[0]; ++I, i = chs[I]) //枚举当前的有数的位置
{
for (rint j = 0; j <= s[i]; ++j) //枚举当前选择j未知数
{
// chu("upd:f[%d][%d]\n",i,j);
for (rint K = 1, k = chs[K]; K < I; ++K, k = chs[K]) //枚举从k位置转移
{
// chu("q[%d]:%d q[%d]:%d\n",i,q[i],k,q[k]);
if (q[i] < q[k])
continue;
for (rint l = 0; l <= min(j, s[k]); ++l) //枚举上一个状态选择了l未知数
{
//目前选了now个未知数
if (!f[k][l])
continue;
// chu("can from:%d %d:%d\n",k,l,f[k][l]);
int now = j - l;
if (s[i] - s[k] >= now && g[q[i] - 1] - g[q[k]] >= now)
upd(f[i][j], (1ll * f[k][l] * C[s[i] - s[k]][now] % mod *
C[g[q[i] - 1] - g[q[k]]][now] % mod) %
mod);
}
}
// chu("f[%d][%d]:%d * fac[%d]:%d\n",i,j,f[i][j],s[n]-j,fac[s[n]-j]);
}
}
int ans = 0;
for (rint i = 0; i <= s[n]; ++i) upd(ans, 1ll * f[n + 1][i] * fac[s[n] - i] % mod);
chu("%d", ans);
return 0;
}
/*
2
1 2
2 1
*/
原文地址：http://www.cnblogs.com/403caorong/p/16881576.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
