AA2MOD无问题2

3.错排问题(problem)
【题目描述】
n本不同的书放在书架上。其中m本书已经重新摆放好,将剩下的n-m 本书也重新摆放,使每本书都不在原来放的位置。
求有几种摆法。
【输入数据】
第1行两个数n,m;
接下来m行,每行两个数xi,yi表示原来的第xi本书已经放到了第yi 个位置上数据保证任意两个x不相同,任意两个y不相同。
【输出数据】
输出方案数,对取模。
【样例输入】
【样例输出】
【样例解释】
(2 1 4 3)、(3 1 4 2)、(4 1 2 3)。
【数据范围】
对于 30% 的数据,n&=10。
对于 60% 的数据,n&=20。
对于100% 的数据,n&=&=xi,yi&=n
题解:非常简单的一道排列问题,就是考场上看到不是很难就放在那,结果只剩10分钟打暴力QAQ。考虑合法方案数非常复杂,但考虑不合法的方案数相对简单,一本书不合法,两本书不合法,三本书不合法……显然要用容斥原理。对于n本书,有n!种排列方式,对于一本书不和发的有(n-1)!种排列,对于已经放了的书,考虑还剩的n-m本书中有s本任然可能不合法,那么
ans=(n-m)!-C(s,1)*(n-m-1)!+C(s,2)*(n-m-2)!-C(s,3)*(n-m-3)!+…+(-1)s*C(s,s)*(n-m-s)!
=Σ(k=0~s) (-1)k*C(s,k)*(n-m-k)!
30分:暴力;
60分:状态压缩dp
100分:组合数学
总结:考场上一定要注意考试技巧,对于月简单的题,越是要花多的时间争取做对,越是难的题先想要朴素做法,在朴素做法的基础上再优化。
#include &iostream&
#include &cstdio&
#include &cstdio&
#include &algorithm&
#define mod
int n,m,last[100000],now[100000];
bool vis[100000],flag[100000];
long long ans=(long long)0;
void dfs(int dep){
if(dep==n+1){
ans=(ans+1)%
if(vis[dep]) dfs(dep+1);
for(int i=1;i&=n;i++){
if(flag[i] || i==dep)
flag[i]=1;dfs(dep+1);flag[i]=0;
int main(){
//freopen(&problem.in&,&r&,stdin);
//freopen(&problem.out&,&w&,stdout);
scanf(&%d%d&,&n,&m);
for(int i=1;i&=m;i++) scanf(&%d%d&,&last[i],&now[i]),vis[last[i]]=1,flag[now[i]]=1;
printf(&%lld\n&,ans);
60分:#include&cstdio&
#include&cstring&
#include&algorithm&
const int mod=;
const int maxn=100005;
int n,m;long long ans=0;
int f[21][1&&20],c[21][21];
bool visit[maxn];
int read()
int x=0;char ch=getchar();
while(ch&57||ch&48) ch=getchar();
while(ch&=48&&ch&=57) x=(x&&1)+(x&&3)+ch-48,ch=getchar();
void work_60()
int sum=(1&&n)-1;int cc=0;
for(int i=1,aa,i&=m;i++)
aa=read();bb=read();
visit[aa]=
cc|=1&&bb-1;
f[0][cc]=1;
for(int i=1;i&=n;i++)
for(int j=0;j&=j++)
if(!f[i-1][j])
if(visit[i])
f[i][j]=f[i-1][j];
for(int k=1;k&=n;k++)
if((j&(1&&k-1))||i==k)
f[i][j|(1&&k-1)]+=f[i-1][j];
f[i][j|(1&&k-1)]%=
printf(&%d\n&,f[n][sum]);
int main()
// freopen(&problem.in&,&r&,stdin);
// freopen(&problem.out&,&w&,stdout);
n=read();m=read();
if(n&=20) work_60();
else printf(&\n&);
}100分:#include &iostream&
#include &cstring&
#include &cstdio&
#include &algorithm&
#define MAXN 100000
int n,m,s=0;
long long mod = (long long);
long long cal[MAXN&&1],inv[MAXN&&1];
bool vis[MAXN],flag[MAXN];
long long del(long long a,long long b){
long long re=(long long)0;
if(b&1) re=(re+a)%
long long get_inv(long long x)
long long ans=1;
long long y=mod-2;
if(y&1) ans=del(ans,x)%
x=del(x,x)%
void init()
int tm=100000;
for(int i=1;i&=i++)
cal[i]=del(cal[i-1],i)%
inv[tm]=get_inv(cal[tm]);
for(int i=tm-1;i&=0;i--)
inv[i]=del(inv[i+1],(i+1))%
long long C(int M,int N){
return del(del(cal[M],inv[N])%mod,inv[M-N])%
int main(){
// freopen(&problem.in&,&r&,stdin);
// freopen(&problem.out&,&w&,stdout);
scanf(&%d%d&,&n,&m);
for(int i=1;i&=m;i++){
scanf(&%d %d&,&x,&y);
vis[x]=1;flag[y]=1;
for(int i=1;i&=n;i++)
if(!flag[i] && !vis[i])
long long ans=cal[n-m];
for(int i=1;i&=s;i++){
if(i&1) ans=(ans-del(C(s,i),cal[(n-m-i)])+mod+mod)%
else ans=(ans+del(C(s,i),cal[(n-m-i)]))%
printf(&%lld\n&,ans);
本文已收录于以下专栏:
相关文章推荐
题目描述传送门题目大意:棋盘是一个n×m的矩形,分成n行m列共n*m个小方格。现在萌萌和南南有C种不同颜色的颜料,他们希望把棋盘用这些颜料染色,并满足以下规定:
棋盘的每一个小方格既可以染...
wangyurzee有n个各不相同的节点,编号从1到n。wangyurzee想在它们之间连n-1条边,从而使它们成为一棵树。
可是wangyurzee发现方案数太多了,于是他又给出了m个限...
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 8129
Accepted: 2...
题意:给出n个数,求出这些数中有多少个三元组(a,b,c),使得(a,b)= 1,(a,c) = 1,(b,c) = 1或
(a,b) != 1,(a,c) != 1,(b,c) != 1。
总概述  
原文 woshi250hua
    专辑的开头贡献一篇容斥原理讲得非常好的文章,讲得十分清楚,很容易就明白容斥原理是什么。
    /v...
UVa 11481 Arrange the Numbers题目大意:可以将序列1,2,3,...n1,2,3,...n任意重排,但重排后的前mm(m≤nm\leq n)个位置恰好有kk(k≤mk\le...
原文http://blog.csdn.net/woshi250hua/article/details/8037106
    专辑的开头贡献一篇容斥原理讲得非常好的文章,讲得十分清楚,...
组合数学之容斥原理在组合数学中,容斥是常常被用到的,我们总用容斥求解一些带有条件的组合数。
容斥原理:具有性质A和性质B的元素个数等同于具有性质A的个数和具有性质B的个数的和再减去同时具有性质A和性质...
How many integers can you find
Problem Description
  Now you get a number N, and a M-integers ...
UVA 10325 The Lottery (组合数学,容斥原理,二进制枚举):http://acm./vjudge/contest/view.action?cid=111598...
他的最新文章
讲师:AI100
讲师:谢梁
您举报文章:
举报原因:
原文地址:
原因补充:
(最多只允许输入30个字)常用软件推荐
原创软件推荐
人工学院2AAMake2Decrypt工具专用于MOD管理,是一款非常实用的工具,直接将PP文件丢到解包器EXE上,即可解包成文件夹,反之文件夹丢到解包器上,捆包成PP文件,如果有同名文件自动备份,后缀.bak需要的玩家赶快下载吧!人工学院2AAMake2Decrypt工具具体操作:1、看你解压缩之后文件夹的文件名,是替换AAEdit,还是替换AAPlay,这两个分别代表人工的***目录下的两个文件夹,简单点说就是AAEdit即学院编辑器目录,而AAPlay是游戏主程序目录。2、看你子文件夹名称,子文件夹名称和游戏***目录中某个文件名是一样的,将该文件复制到AAMake2Decrypt.exe所在文件夹,然后拖拽该文件到AAMake2Decrypt.exe程序上,该文件会被***成一个文件夹,然后捡你上面图示的文件替换该文件夹内的同名文件,替换后再将该文件夹拖拽到AAMake2Decrypt.exe程序上,替换后的文件夹又会被重新生成同名文件,然后将生成后的文件复制回学院的原目录,覆盖原文件即可。
人工学院是日本著名3D游戏公司ILLUSION于日发售的继承《人工少女》、《人工少女2》、《人工少女3》之后的人工系列最新3D***游戏作品,下面是小凡整理制作的人工学院MOD大全专题,提供去马赛克、服饰等补丁,需要的可以来看下哦。
人工学院动漫人物mod整合包,是一个包括saber、凛...
人工学院2AAMake2Decrypt工具专用于MOD管理,是一...
人工学院2果体四连发MOD,将图片复制到data/S***E/...
人工学院美女MOD合集,有78个美女可供选择,总有...
高速下载器地址
适合机型:三星G9350,三星G9350 ROM
Android版本:7.0
ROM大小:1810 MB
本站提供的软件会测试再上传,但无法保证所有软件都没有问题,如果您发现链接错误或其它问题,请在评论里告诉我们!
下载点支持点击下载(IE图标)或(迅雷图标),若直接点击下载速度太慢,请尝试点击其他的下载点,若文件太大请使用高速下载器。为确保下载的文件能正常使用,请使用最新版本解压本站软件。
建议大家谨慎对待所下载的文件,大家在***的时候务必留意每一步!关于或的有关提示,请自行注意选择操作。
本站所有资源均是软件作者、开发商投稿、网上搜集,任何涉及商业盈利目的均不得使用,否则产生的一切后果将由您自己承担!将不对任何资源负法律责任。所有资源请在下载后24小时内删除。
本站下载资源全部由软件作者或软件厂商提供,游戏相关下载转自各大游戏论坛及游戏下载站,并全部为免费分享。如侵犯了您的版权,请立刻联系我们并附带版权证明,本站将尽快处理删除(举报联系QQ:3909136),或。
若您下载的资源有问题或无法下载,请与本站***人员联系(QQ:9190104)。

我要回帖

更多关于 小米mix2问题 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信