題目鏈接：點擊查看
題目大意：初始時有一個二維平面， 平面上給出 n 條蛇，現(xiàn)在可以選擇 m 條不同的蛇進行捕殺，當選擇了某條蛇，其所在的坐標可以覆蓋到的半徑為 r 的范圍內(nèi)的蛇都會被捕殺，更確切的說，選擇了位置 ( x , y ) 的蛇，那么 ( x - r , y - r ) ~ ( x + r , y + r ) 這個矩形內(nèi)的蛇都會被捕殺，每條蛇都有自己的價值，每次捕殺的價值是(所有被捕殺的蛇的價值和)的平方，問所有方案的價值和是多少
題目分析：比較巧妙的一道容斥題目，首先看到平方應該順著去思考，而不是我行我素的去思考每條蛇單獨的貢獻
利用完全平方公式將平方和拆開：
如果增加變量的個數(shù)，不難看出實際上也是兩層 for 循環(huán)可以表達出來的一個求和公式
所以我們不妨去考慮每一對蛇 ( i , j ) 的貢獻，直接求交集是比較困難的，但是正難則反，可以思考求交集的補集，那么利用容斥推一下公式：
同時包含蛇 i 和蛇 j 的方案 = 總方案?- ( 不同時包含蛇 i 和蛇 j 的方案?) 不同時包含蛇 i 和蛇 j 的方案 = 不包含蛇 i 的方案?+?不包含蛇 j 的方案?-?不包含蛇 i 也不包含蛇 j 的方案 不包含蛇 i 也不包含蛇 j 的方案?= 不包括 { ( 蛇 i 的捕殺矩形 ) 與 ( 蛇 j 的捕殺矩形 ) 的并集 } 的方案 =?{ 全集 - ( 蛇 i 的捕殺矩形 ) 與 ( 蛇 j 的捕殺矩形 ) 的并集 } 的方案 ( 蛇 i 的捕殺矩形 ) 與 ( 蛇 j 的捕殺矩形 ) 的并集 = 蛇 i 后的捕殺矩形 +蛇 j 后的捕殺矩形 - ( 蛇 i 的捕殺矩形 與 蛇 j 的捕殺矩形 的面積交集 ) 不難發(fā)現(xiàn)一步步遞推是可以間接求出我們所想要求出的答案的，關(guān)于最后的那個矩形面積，用二維前綴和求一下就好了，其余的用組合數(shù)學求解一下即可
補充一下關(guān)于矩形的交集，實質(zhì)上是兩條線段的交集，這個在紙上稍微畫一下就明白了
代碼：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e3+100;const int mod=1e9+7;int x[N],y[N],maze[N][N];LL fac[N],inv[N],b[N];LL q_pow(LL a,LL b)
{LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}LL C(int n,int m)
{if(n<m)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}int cal(int x1,int y1,int x2,int y2)
{if(x1>x2||y1>y2)return 0;x1=max(x1,1),y1=max(y1,1);x2=min(x2,1000),y2=min(y2,1000);return maze[x2][y2]-maze[x2][y1-1]-maze[x1-1][y2]+maze[x1-1][y1-1];
}void init()
{fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;inv[N-1]=q_pow(fac[N-1],mod-2);for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.ans.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();int n,m,r;scanf("%d%d%d",&n,&m,&r);for(int i=1;i<=n;i++){scanf("%d%d%lld",x+i,y+i,b+i);maze[x[i]][y[i]]++;}for(int i=1;i<=1000;i++)for(int j=1;j<=1000;j++)maze[i][j]+=maze[i-1][j]+maze[i][j-1]-maze[i-1][j-1];LL ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){LL res=b[i]*b[j]%mod;LL cnt=C(n,m);LL noi=C(n-cal(x[i]-r,y[i]-r,x[i]+r,y[i]+r),m);LL noj=C(n-cal(x[j]-r,y[j]-r,x[j]+r,y[j]+r),m);LL noij=C(n-cal(x[i]-r,y[i]-r,x[i]+r,y[i]+r)-cal(x[j]-r,y[j]-r,x[j]+r,y[j]+r)+cal(max(x[i]-r,x[j]-r),max(y[i]-r,y[j]-r),min(x[i]+r,x[j]+r),min(y[i]+r,y[j]+r)),m);cnt=((cnt-noi-noj+noij)%mod+mod)%mod;res=cnt*res%mod;ans=(ans+res)%mod;}printf("%lld\n",ans);return 0;
}
?
總結(jié)
以上是生活随笔 為你收集整理的CodeForces - 1425D Danger of Mad Snakes(容斥+组合数学) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
