The Review Plan I-禁位排列和容斥原理
The Review Plan I
Michael takes the Discrete Mathematics course in this semester. Now it's close to the final exam, and he wants to take a complete review of this course.
The whole book he needs to review has N chapter, because of the knowledge system of the course is kinds of discrete as its name, and due to his perfectionism, he wants to arrange exactly N days to take his review, and one chapter by each day.
But at the same time, he has other courses to review and he also has to take time to hang out with his girlfriend or do some other things. So the free time he has in each day is different, he can not finish a big chapter in some particular busy days.
To make his perfect review plan, he needs you to help him.
Input
There are multiple test cases. For each test case:
The first line contains two integers N(1≤N≤50), M(0≤M≤25), N is the number of the days and also the number of the chapters in the book.
Then followed by M lines. Each line contains two integers D(1≤D≤N) and C(1≤C≤N), means at the Dth day he can not finish the review of the Cth chapter.
There is a blank line between every two cases.
Process to the end of input.
Output
One line for each case. The number of the different appropriate plans module 55566677.
Sample Input
4 3
1 2
4 3
2 1 6 5
1 1
2 6
3 5
4 4
3 4
Sample Output
11
284
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
#define mod 55566677
long long day[],zhang[],c[],i,ss,m,n,gx[][];
struct PP
{
int d,z;
}chi[];
int rc(int x,int y)
{
if(x>=m)
{
if(y&)ss-=c[n-y];
else ss+=c[n-y];
ss%=mod;
ss=(ss+mod)%mod;
return ;
}
rc(x+,y);
if(day[chi[x].d]==&&zhang[chi[x].z]==)
{
day[chi[x].d]=;zhang[chi[x].z]=;
rc(x+,y+);
day[chi[x].d]=;zhang[chi[x].z]=;
}
}
int main()
{
c[]=;c[]=;
for(i=;i<=;i++)c[i]=(c[i-]*i)%mod;
while(cin>>n>>m&&n+m!=)
{
ss=;
memset(day,,sizeof(day));
memset(zhang,,sizeof(zhang));
memset(gx,,sizeof(gx));
for(i=;i<m;i++)
{
cin>>chi[i].d>>chi[i].z;
if(gx[chi[i].d][chi[i].z]==)gx[chi[i].d][chi[i].z]=;
else {m--;i--;}
}
rc(,);
ss=(ss+mod)%mod;
cout<<ss<<endl;
}
return ;
}
最新文章
- linux 安装 ArcSDE10.1
- cocos2d-x WebSocket
- Codeigniter CRUD生成工具
- Linux之date
- 【转】linux expr命令参数及用法详解
- Notice: Undefined offset 的解决方法
- Mysql 学习笔记 20140219
- leetcode@ [329] Longest Increasing Path in a Matrix (DFS + 记忆化搜索)
- jquery动态插入行
- HW4.11
- Python4Delphi也是与VCL密切相关,所以才能相互调用,绝对有研究价值!
- HDU 4982 Goffi and Squary Partition(推理)
- 使用POST下载文件
- CodeForce Div 2 C. Masha and two friends
- 一键部署office的工具——OTool
- Zepto整体概况
- net core体系-web应用程序-4net core2.0大白话带你入门-7asp.net core日志组件(Logger和Nlog)
- CodeForces - 615D Multipliers(数论)
- Sysfs文件系统接口调试
- iframe 常见问题 解析