校oj很多题目还是很好的 考虑给他们蟹蟹题解
打扫卫生 题目大意：n个房间 m个同学 每个房间至少两个同学 求方案数
显然是个计数类的题目 技术类题目 真的 需要有一定数学感觉8... 头有点大奥
然后我们考虑这道题目显然是一个组合数的问题 然后需要用到隔板法 所以在这里 我浅析一下隔板法的应用 有多学习了一个好东西
具体隔板法 对于n个有顺序的球 我们考虑在中间放入m个板 然后规定我们不能在两个球之间放两个及以上个隔板 然后两段不能放隔板 问你方案数
我们不妨考虑 在这n-1个空位置 放入m个球 那么方案数 显然是$\binom{n-1}{m}$
据说今年高联数学二试也考了个隔板法？？ 还是比较好写的那个题目 到底是形如什么样的式子 可以 使用隔板法求解问题呢
我们不妨举几个例子
求解$\sum_{i=1}^{m} x_i=n$ 有多少个正整数解
对于这种情况 我们可以考虑是在n个球中插入了 m-1个板 类比刚才的方法 容易得到方案数数为$\binom{n-1}{m-1}$
然后考虑 对于求解$\sum_{i=1}^{m} x_i=n$ 有多少个自然数解 也就是说 你可以存在$x_i=0$ 所以我们为了避免这种情况出现
我们可以对于每一个$x_i+1$ 所以 我们的式子变成了 $\sum_{i=1}^{m} (x_i+1)=n+m$ 所以此时换元 每一个$t_i$ 就是正整数了
所以我们可以类比刚才的方法做了 然后方案数就是$\binom{n+m-1}{m-1}=\binom{n+m-1}{n}$
然后这道题目保证每个房间至少两个人 所以我们不妨 先将这 n*2个同学T出去 因为一定要留下来这2*n个同学 至于剩下的m-2*n个同学
我们考虑 转化成刚才我们讨论过的问题 我们除去这些2*n个人之后 我们 每个房间的人数$x_i$ 这时候就是求解 $\sum_{i=1}^{n} x_i=m-2*n$
对于这种情况 我们$x_i$ 存在 等于0的情况 我们进一步 转化成 整数情况 $\sum_{i=1}^{n} (x_i+1)=m-2*n+n$ 然后类比刚才的例子1 我们就求出了答案
果然是讨论问题 所以这个题目 还有写 高精*单精 就没了
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x*=f; } const int N=1010; int n,m,top,b[N],p0[N],p1[N],p2[N]; inline void insert(int x,int *a) { int now=x; for(int i=2;i*i<=x;i++) { while(now%i==0) { now=now/i; ++a[i]; } } if(now>1) ++a[now]; } inline void mul(int x) { int res=0; for(int i=1;i<=top;i++) { b[i]=b[i]*x; b[i]+=res; res=b[i]/10; b[i]=b[i]%10; } while(res) { b[++top]=res; res=b[top]/10; b[top]=b[top]%10; } } int main() { read(n); read(m); if(m<2*n) {puts("0");return 0;} int s=m-2*n+n-1,c=m-2*n; for(int i=2;i<=s;i++) insert(i,p0); for(int i=2;i<=c;i++) insert(i,p1); for(int i=2;i<=s-c;i++) insert(i,p2); b[++top]=1; for(int i=2;i<=s;i++) { p0[i]=p0[i]-p1[i]-p2[i]; while(p0[i]) { --p0[i]; mul(i); } } for(int i=top;i>=1;i--) printf("%d",b[i]); return 0; }
pigs 一道很有意思的网络流呢 这个建图 我着实 思考了一会 不过在Chdy的指导下 还是搞出来了
具体怎么建图呢
原文：https://www.cnblogs.com/Tyouchie/p/11591966.html
