https://www.cnblogs.com/wzxbeliever/p/16484848.html
这是一道非常好的容斥题目
求矩形的并集 并且可以在规定区域内求矩形的并集
https://www.luogu.com.cn/problem/P1450
分析：一道非常牛逼的容斥
如果我们就赤裸裸的多重背包肯定超时
那么怎么办呢？如果没有硬币数量的限制那就多好啊？直接一个完全背包预处理，然后O(1)输出就好了
可是有了硬币的限制怎么办？我们先考虑一个简单一点的情况：只有第一个硬币有限制。
我们先完全背包预处理好无限制的情况，拿dp[tot]减去dp[tot-c[i]*(d[i]+1)]就是我们所需的方案数
无限制的情况就是没有那个di，而有限制时，不应该计入答案的方案数就是把c[i]这个硬币取了超过d[i]次，对吧？
那么我们手动先取出d[i]+1个c[i]的硬币，然后剩下的价值弄个完全背包，这时就是我们所不需要的答案， 把它减掉就行了。
为什么是c[i](d[i]+1) 而不是 c[i]d[i]?
取c[i]*d[i]剩下的容量 也是跑的所有硬币的完全背包 可能就会有c[i]没有用到的情况 这样c[i]的个数还是d[i]个 还是合法的
所以我们取c[i]*(d[i]+1) 这样一定能保证c[i]是取超了的
这样四个硬币直接容斥一下就好了
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
void solve();
int d[5],c[5],s;
ll dp[maxn],ans;
int main(){
for(int i=1;i<=4;i++)cin>>c[i];
int T;cin>>T;
while(T--)solve();
return 0;
}
void solve(){
memset(dp,0,sizeof(dp));
for(int i=1;i<=4;i++)cin>>d[i];
cin>>s;
dp[0]=1;ans=0;
for(int i=1;i<=4;i++)
for(int j=0;j+c[i]<maxn;j++)
dp[j+c[i]]+=dp[j];
int S=1<<4;
for(int i=0;i<S;i++){
int p=__builtin_popcount(i);
int res=0;
for(int j=0;j<=3;j++)
if((i>>j)&1)res+=(d[j+1]+1)*c[j+1];
if(s>=res){
if(p&1)ans-=dp[s-res];
else ans+=dp[s-res];
}
}
cout<<ans<<endl;
}
想起了之前比赛的一道题目
一个序列 给定一个最大值max 最小值min 求有多少子序列满足最大值为max 最小值为min
分析：设calc(L,R)表示满足取值范围在[L,R]的子序列个数
这个很好处理 只要线性扫过去就行
但是题目要求一定要取到最小一定是L 最大一定是R
正难则反 很容易想到容斥
只取到了L：calc(L,R-1)
只取到了R: calc(L+1,R)
两个都没取到:calc(L+1,R-1)
ANS=calc(L,R)-calc(L+1,R)-calc(L,R-1)+calc(L+1,R-1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 200010;
LL n, a[N];
LL ans;
void solve(LL x, LL y, LL t) {
int lst = 1;
for(int i = 1; i <= n; ++ i) {
if(a[i] > x or a[i] < y) {
lst = i + 1;
}
ans += (i - lst + 1) * t;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
LL x, y;
cin >> n >> x >> y;
for(int i = 1; i <= n; ++ i) cin >> a[i];
solve(x, y, 1);
solve(x - 1, y, -1);
solve(x, y + 1, -1);
solve(x - 1, y + 1, 1);
cout << ans << "\n";
return 0;
}
P3813 [FJOI2017] 矩阵填数
一道非常好的容斥题目
分析：
#include<cstdio>
#include<algorithm>
using namespace std;const int N=15;const int M=1050;typedef long long ll;const ll mod=1e9+7;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod){if(p&1){r=r*a%mod;}}return r;}
int n;int m;ll h;ll w;ll s[M];ll u[M];int up;int siz[M];ll res;int T;
struct retc//矩形类
{
ll x;ll y;ll x1;ll y1;int v;
inline void rd(){scanf("%lld%lld%lld%lld%d",&x,&y,&x1,&y1,&v);}
inline bool ck(){return (x>x1)||(y>y1);}//是否为空
inline ll calcs(){return (x1-x+1)*(y1-y+1);}//求面积
void operator &=(const retc& a)//交
{x=max(x,a.x);y=max(y,a.y);x1=min(x1,a.x1);y1=min(y1,a.y1);}
friend bool operator <(retc a,retc b){return a.v<b.v;}
}r[N],tr;
inline void solve()
{
scanf("%lld%lld%d%d",&h,&w,&m,&n);
for(int i=0;i<n;i++){r[i].rd();}sort(r,r+n);up=(1<<n)-1;
for(int i=1;i<=up;i++)//暴力求交集面积
{
tr.x=1;tr.y=1;tr.x1=h;tr.y1=w;
for(int p=i,j=0;p;p>>=1,j++){if(p&1){tr&=r[j];if(tr.ck()){s[i]=0;goto ed;}}}
s[i]=tr.calcs();ed:;
}
for(int i=1;i<=up;i++)//暴力求并集面积
{
for(int j=i;j;j=(j-1)&i)
{if(siz[j]%2){u[i]+=s[j];}else {u[i]-=s[j];}}//奇数相加 偶数相减
}
int ns=0;int ls=0;res=1;
for(int i=0;i<n;i++)//分值域统计方案数
{
ns|=(1<<i);if(r[i].v==r[i+1].v){continue;}
ll tot=u[ns|ls]-u[ls];
ll st=tot;
ll ret=po(r[i].v,tot);
for(int k=ns;k;k=(k-1)&ns)
{
tot=u[k|ls]-u[ls];
ll del=po(r[i].v-1,tot)*po(r[i].v,st-tot)%mod;
if(siz[k]%2){ret=(ret+mod-del)%mod;}
else {ret=(ret+del)%mod;}
}res=res*ret%mod;ls|=ns;ns=0;//乘起来
}printf("%lld\n",res*po(m,h*w-u[up])%mod);
}
inline void clear(){for(int i=0;i<=up;i++){u[i]=0;}}
int main()
{
for(int i=1;i<=1023;i++){siz[i]=siz[i>>1]+(i&1);}scanf("%d",&T);
for(int z=1;z<=T;z++){solve();clear();}return 0;//拜拜程序~
}
P5505 [JSOI2011] 分特产
还是感觉没有把容斥搞透彻
分析：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
const int mod=1e9+7;
int c[2005][2005],n,m,a[2005];
int pow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
a*a%mod;
b>>=1;
}
return ans;
}
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d",&a[i]);
for(int i=0;i<=2000;i++)
c[i][i]=c[i][0]=1;
for(int i=1;i<=2000;i++)
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
int ans=0;
for(int i=0;i<=n-1;i++)
{
int cnt=1;
for(int j=1;j<=m;j++)
cnt=cnt*c[n+a[j]-i-1][n-i-1]%mod,cnt%=mod;
if(i%2)ans=(ans-cnt*c[n][i]%mod+mod)%mod;
else ans=(ans+cnt*c[n][i]%mod)%mod;
}
printf("%d\n",ans);
return 0;
}
P6076 [JSOI2015] 染色问题
分析：
总结：
灵魂操作 每种颜色都至少出现一次 相当于求交集 这样用容斥即可
现在怎么处理行和列的限制
我们依次考虑每一列 要保证每一行都要有颜色 只要保证每一行 取列的情况没有全空
现在问题还要保证每列都要有颜色 所以问题又变成了求交集 这样还是用容斥
因为每一行的情况是独立的 所以我们每次强制每一行都是选的那几列
这操作真的太牛逼了
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int SIZE = 4e2 + 5;
const int mod = 1e9 + 7;
int n, m, c;
int inv[SIZE], fac[SIZE], f[SIZE];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (c < 48 || c > 57) b ^= c == '-', c = fetch();
while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
return b ? a : -a;
}
} using GTR::read;
int qPow(int a, int b) {
int ans = 1ll;
for ( ; b; b >>= 1, a = a * a % mod) {
if (b & 1) ans = ans * a % mod;
}
return ans % mod;
}
void init() {
const int N = 4e2;
fac[0] = 1ll;
for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod;
inv[N] = qPow(fac[N], mod - 2ll);
for (int i = N - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int x, int y) {
if (x < y) return 0ll;
return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
signed main() {
n = read(), m = read(), c = read(); init();
for (int i = 1; i <= c; ++ i) {
f[i] = (qPow(i + 1, m) - 1ll + mod) % mod, f[i] = qPow(f[i], n) % mod;
int res = 0;
for (int k = 1; k <= m; ++ k) {
int pw = (qPow(i + 1, m - k) - 1ll + mod) % mod; pw = qPow(pw, n) % mod;
if ((k - 1) & 1) res = (res - (pw * C(m, k) % mod) + mod) % mod;
else res = (res + (pw * C(m, k) % mod)) % mod;
}
f[i] = (f[i] - res + mod) % mod;
}
int ans = f[c], res = 0;
for (int i = 1; i <= c; ++ i) {
if ((i - 1) & 1) res = (res - (C(c, i) * f[c - i] % mod) + mod) % mod;
else res = (res + (C(c, i) * f[c - i] % mod)) % mod;
}
printf("%lld\n", (ans - res + mod) % mod);
return 0;
}