放棋子(chess.pas/c/cpp)
题目大意
现在有一个 n*m 的棋盘，现在你需要在棋盘上摆放 2n 个棋子，要求满足如下条件：
1、 每一列只能有一个棋子；
2、 每一行的前 xi 个格子有一个棋子，而且最多有一个棋子；
3、 每一行的后 yi 个格子有一个棋子，而且最多有一个棋子；
求一共有多少种不同的放置方案，答案对于 1000000007 取模
输入文件
输入文件为 chess.in。
输入共有 n+1 行。第一行有两个整数 n,m，表示该棋盘的行数与列数。
接下来的 n 行，每行两个整数 xi 和 yi，表示每一行的前 xi 个格子需要有一个棋子，每
一行的后 yi 个格子需要有一个棋子。
输出文件
输出文件为 chess.out。
输出一个整数表示共有多少种不同的方案，答案对于 1000000007 取模。
样例输入
3 6
1 2
3 3
3 2
样例输出
4
数据规模与约定
n<=50 m<=200
对于所有的 i，有 xi+yi≤m。
——————————————————————————题解
首先60分我们只需要拿乘法原理算算算就可以了（把x,y排列顺序不影响结果，那就变成排列后左边对于第一行有x1中方法，第二行有x2-1种，第n行有xn-n+1种，乘法原理乘起来就好了，右边同理，然后左右方案数相乘）因为最大的xi和最大的yi不会重合，但是如果他们最大重合了就要换一个做法
首先我们左边从小到大，右边从大到小这么想，因为xi+yi≤m，所以方块排序后不会重叠，只是一列可能有两种颜色
然后从左往右扫
然后我们对右边来说事，也是从左往右扫，才能把两者结合在一起
然后我们发现这只与i(扫到第几行)，k(选了几个数)，j(右边可以放几个)有关，然后我们把两边结合到一起
得到：
不在右边放f[i+1][j+p][k+z]+=f[i][j][k]*A(i-k,z)
在右边放f[i+1][j-1+p][k+z+1]+=f[i][j][k]*j
最后的答案是f[m+1][0][2*n]，因为到了m列的时候右边还是可以放的
啊累死我了……本题结束了……下面是代码……
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define mo 1000000007
#define siji(i,x,y) for(int i=(x);i<=(y);i++)
#define gongzi(j,x,y) for(int j=(x);j>=(y);j--)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);i++)
#define sigongzi(j,x,y) for(int j=(x);j>(y);j--)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,m,x[],y[],z[],p[],b[],c[];
int a[][];
void anm() {
siji(i,,) a[i][]=;
siji(i,,) {
siji(j,,) {
a[i][j]=1LL*i*a[i-][j-]%mo;
}
}
}
void init() {
scanf("%d%d",&n,&m);
if(m<*n) {puts("");exit();}
siji(i,,n) {
scanf("%d%d",&x[i],&y[i]);
z[x[i]]++;
p[m-y[i]]++;//这是下一列要有的右端开头
}
siji(i,,m) b[i]=b[i-]+p[i-];//这是个常数优化，加上后快到飞起
siji(i,,m) c[i]=c[i-]+z[i];//同上
anm();//组合数预处理
}
int f[][][];//f(i,j,k)
void solve() {
f[][][]=;//初始化
siji(i,,m) {
siji(j,,b[i]) {//可以改成0-n
siji(k,c[i-],i) {//可以改成0-m
f[i+][j+p[i]][k+z[i]]=(f[i+][j+p[i]][k+z[i]]+1LL*f[i][j][k]*a[i-k][z[i]])%mo;
if(j-+p[i]>=)
f[i+][j-+p[i]][k+z[i]+]=(f[i+][j-+p[i]][k+z[i]+]+1LL*j*f[i][j][k]*a[i-k-][z[i]])%mo; }
}
}
printf("%d\n",f[m+][][*n]);
}
int main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
init();
solve();
}