做文章网站,wordpress+布局插件,广东省住建局官网,wordpress素材网主题题目 给n个人安排座位#xff0c;先给每个人一个1~n的编号#xff0c;设第i个人的编号为ai#xff08;不同人的编号可以相同#xff09;#xff0c;接着从第一个人开始#xff0c;大家依次入座#xff0c;第i个人来了以后尝试坐到ai#xff0c;如果ai被占据了#xff…题目 给n个人安排座位先给每个人一个1~n的编号设第i个人的编号为ai不同人的编号可以相同接着从第一个人开始大家依次入座第i个人来了以后尝试坐到ai如果ai被占据了就尝试ai1ai1也被占据了的话就尝试ai2……如果一直尝试到第n个都不行该安排方案就不合法。然而有m个人的编号已经确定(他们或许贿赂了你的上司...)你只能安排剩下的人的编号求有多少种合法的安排方案。由于答案可能很大只需输出其除以M后的余数即可。 输入格式 第一行一个整数T表示数据组数 对于每组数据第一行有三个整数分别表示n、m、M 若m不为0则接下来一行有m对整数p1、q1p2、q2 ,…, pm、qm其中第i对整数pi、qi表示第pi个人的编号必须为qi 输出格式 对于每组数据输出一行若是有解则输出YES后跟一个整数表示方案数mod M注意YES和数之间只有一个空格否则输出NO 输入样例 2 4 3 10 1 2 2 1 3 1 10 3 8882 7 9 2 9 5 10 输出样例 YES 4 NO 提示 100%的数据满足1≤T≤101≤n≤3000≤m≤n2≤M≤1091≤pi、qi≤n 且保证pi互不相同。 题解 容易发现其实这是插入顺序无关的 位置插入是否合法只要看这个位置及其之后是否坐满 直接难以计算一个位置之后坐了多少 但是坐到一个位置前的人的编号一定比这个位置小 如果编号为一个位置及其之前的位置的人数小于这个位置的编号说明前面的座位一定坐不满那么就代表着不合法 所以我们设\(f[i][j]\)表示编号为第\(i\)个位置及其之前的人数有\(j\)人的方案数 就可以枚举\(i\)号位坐了多少人进行转移了 我们记一个\(sum[i]\)数组表示固定编号\(i\)的人数 并且将没有固定编号的人数记为编号\(0\) 这样子一个位置可以坐的人数就在范围\([num[i],sum[i]]\)以内了其中\(num[i]\)指固定编号为\(i\)的人数 #includeiostream
#includecstdio
#includecmath
#includecstring
#includealgorithm
#define LL long long int
#define Redge(u) for (int k h[u],to; k; k ed[k].nxt)
#define REP(i,n) for (int i 1; i (n); i)
#define BUG(s,n) for (int i 1; i (n); i) couts[i] ; puts();
using namespace std;
const int maxn 305,maxm 100005,INF 1000000000;
inline int read(){int out 0,flag 1; char c getchar();while (c 48 || c 57){if (c -) flag -1; c getchar();}while (c 48 c 57){out (out 3) (out 1) c - 48; c getchar();}return out * flag;
}
int P,n,m;
LL C[maxn][maxn],f[maxn][maxn],sum[maxn],num[maxn];
void init(){memset(f,0,sizeof(f));memset(sum,0,sizeof(sum));memset(num,0,sizeof(num));C[0][0] 1;for (int i 1; i n; i){C[i][0] C[i][i] 1;for (int j 1; j (i 1); j)C[i][j] C[i][i - j] (C[i - 1][j - 1] C[i - 1][j]) % P;}
}
int main(){int T read(),flag;while (T--){n read(); m read(); P read(); flag true;init(); sum[0] n - m;for (int i 1; i m; i) read(),num[read()];for (int i 1; i n; i){sum[i] sum[i - 1] num[i];if (sum[i] i) {flag false; break;}}if (!flag){puts(NO); continue;}f[0][0] 1;for (int i 1; i n; i){for (int j i; j sum[i]; j){for (int k num[i]; k j - i 1; k)f[i][j] (f[i][j] f[i - 1][j - k] * C[sum[i] - num[i] - (j - k)][k - num[i]] % P) % P;}}printf(YES %lld\n,f[n][n]);}return 0;
}转载于:https://www.cnblogs.com/Mychael/p/8881630.html
