傳送門

文章目錄

• 題意：
• 思路：

題意：

有$n$組物品，每組有$a_i$個肉和$b_i$個菜，你可以選擇兩組物品讓后將肉和菜其串在一根串上，問有多少種不同的串法。
兩種方法不同當且僅當選的物品不同或者串的順序存在至少一個位置一個方法串的肉，另一個串的菜。
$n\le 2e5,a_i,b_i\le 2e3$

思路：

一個比較巧妙的建模題。

考慮暴力做法，顯然答案為${\sum }_{i=1}^n{\sum }_{j=i+1}^n\left(\genfrac{}{}{0ex}{}{a_i+b_i+a_j+b_j}{a_i+a_j}\right)$，但是這個是$n^2$的，而且基本沒什么能優(yōu)化的地方。
看到$a_i,b_i$很小，可以考慮從這里入手。
枚舉$a$？也是行不通的。。
還是觀察一下式子吧，將其抽象一下，考慮到平面兩個點$(x_1,y_1),(x_2,y_2)$，從第一個點到第二個點的路徑方案數(shù)為$\left(\genfrac{}{}{0ex}{}{x_2?x_1+y_2?y_1}{x_2?x_1}\right)$。
嗯？！這兩個式子是不是像極了！
我們只需要將其中一個$(a_i,b_i)$變成負數(shù)就行了！
所以我們要求的東西變成什么了？
不就是從${\sum }_{j=i+1}^{n}path((?a_j,?b_j),(a_i,b_i))$的方案數(shù)嘛。
這個好算啊，直接轉(zhuǎn)換成二維平面的$dp$，讓后$$f[i][j]=f[i?1][j]+f[i][j?1]$$
但是你會發(fā)現(xiàn)一個問題，這個是求的${\sum }_{j=1}^{n}path((?a_j,?b_j),(a_i,b_i))$，但是你要求${\sum }_{j=i+1}^{n}path((?a_j,?b_j),(a_i,b_i))$，顯然我們簡單容斥一下，將原來的式子${\sum }_{i=1}^n{\sum }_{j=i+1}^n\left(\genfrac{}{}{0ex}{}{a_i+b_i+a_j+b_j}{a_i+a_j}\right)=\frac{({\sum }_{i=1}^n{\sum }_{j=1}^n(\genfrac{}{}{0ex}{}{a_i+b_i+a_j+b_j}{a_i+a_j})?{\sum }_{i=1}^n(\genfrac{}{}{0ex}{}{2?(a_i+b_i)}{2?a_i}))}{2}$
這樣問題就解決啦。

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=2000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],b[N]; LL f[4010][4010]; LL inv[N],fun[N];LL C(int a,int b) {if(a<0||b<0||a<b) return 0;return fun[a]*inv[b]%mod*inv[a-b]%mod; }LL qmi(LL a,LL b) {LL ans=1%mod;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);inv[1]=1;fun[0]=fun[1]=1;for(int i=2;i<N;i++)fun[i]=fun[i-1]*i%mod;inv[N-1]=qmi(fun[N-1],mod-2);for(int i=N-2;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%mod;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),f[2001-a[i]][2001-b[i]]++;for(int i=1;i<=4005;i++) {for(int j=1;j<=4005;j++) {(f[i][j]+=f[i-1][j])%=mod;(f[i][j]+=f[i][j-1])%=mod;}}LL ans=0;for(int i=1;i<=n;i++) {ans+=f[2001+a[i]][2001+b[i]]; ans%=mod;ans-=C(2*(a[i]+b[i]),2*a[i]); ans%=mod;ans+=mod; ans%=mod;}cout<<ans*qmi(2,mod-2)%mod<<endl;return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的BBQ Hard dp + 组合数学 + 建模的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。