企业形象型网站建设,上海开艺设计集团有限公司,html软件官方下载,广告设计免费题目描述 一个长度为 $n$ 的序列#xff0c;每个位置为 $0$ 或 $1$ 两种。现在给出 $m$ 个限制条件#xff0c;第 $i$ 个限制条件给出 $x_i$ 、$y_i$ #xff0c;要求至少满足以下两个条件之一#xff1a; 序列的前 $x_i$ 个位置中#xff0c;恰好有 $y_i$ 个 $1$ #x… 题目描述 一个长度为 $n$ 的序列每个位置为 $0$ 或 $1$ 两种。现在给出 $m$ 个限制条件第 $i$ 个限制条件给出 $x_i$ 、$y_i$ 要求至少满足以下两个条件之一 序列的前 $x_i$ 个位置中恰好有 $y_i$ 个 $1$ 序列的后 $y_i$ 个位置中恰好有 $x_i$ 个 $1$ 求有多少个序列满足所有限制条件。答案可能很大只需要输出它对 $998244353$ 取模后的结果即可。 题解 组合数乱搞 显然当 $xy$ 时条件为前缀限制$xy$ 时条件为后缀限制。 既有前缀限制又有后缀限制的情况下我们枚举总共1的个数把后缀限制转化为前缀限制。 如果所有限制均有 $x\ne y$ 则可以直接使用组合数计算。预处理组合数单次计算的时间复杂度是 $O(n)$ 的。 当有 $xy$ 时显然只需要考虑所有 $xy$ 限制中 $x$ 最大的限制即可总方案数为 满足前缀满足后缀-满足前缀和后缀。 时间复杂度 $O(n^2)$ 。 #include cstdio
#include cstring
#include algorithm
#define N 1010
#define M 5010
#define mod 998244353
using namespace std;
int n , ax[N] , ay[N] , at , bx[N] , by[N] , bt , c[M][M] , v[M];
int solve(int x)
{int i , last 0 , ans 1;memset(v , -1 , sizeof(v));v[0] 0 , v[n] x;for(i 1 ; i at ; i ){if(v[ax[i]] ! -1 v[ax[i]] ! ay[i]) return 0;v[ax[i]] ay[i];}for(i 1 ; i bt ; i ){if(v[n - bx[i]] ! -1 v[n - bx[i]] ! x - by[i]) return 0;v[n - bx[i]] x - by[i];}for(i 1 ; i n ; i ){if(v[i] ! -1){if(v[i] v[last]) return 0;ans 1ll * ans * c[i - last][v[i] - v[last]] % mod , last i;}}return ans;
}
int main()
{int T;scanf(%d , T);while(T -- ){at bt 0;int m , i , j , x , y , p 0 , mx 0 , ans 0;scanf(%d%d , n , m);for(i 1 ; i m ; i ){scanf(%d%d , x , y) , mx max(mx , min(x , y));if(x y) ax[at] x , ay[at] y;else if(x y) bx[bt] y , by[bt] x;else p max(p , x);}c[0][0] 1;for(i 1 ; i n ; i ){c[i][0] 1;for(j 1 ; j i ; j )c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % mod;}for(i mx ; i n ; i ){at , ax[at] ay[at] p , ans (ans solve(i)) % mod;bt , bx[bt] by[bt] p , ans (ans - solve(i) mod) % mod;at -- , ans (ans solve(i)) % mod , bt -- ;}printf(%d\n , ans);}return 0;
}转载于:https://www.cnblogs.com/GXZlegend/p/8681422.html
