傳送門

題意：$T$組詢問$N$個相同物品選不超過$K$個的方案數(shù)，$T,N\le 1e5$

設(shè)$f(x,y)={\sum }_{i=0}^y{C}_x^i$即所求

直接求并沒有很好的性質(zhì)

但我們發(fā)現(xiàn):$f(x,y)=2f(x?1,y)?C_{x?1}^y$，即乘以二減去最后一個等于下一行

由$C_n^m=C_{n?1}^m+C_{n?1}^{m?1}$,只有最后一個出現(xiàn)一次，其余出現(xiàn)兩次

而$f(x,y)到$$f(x,y\pm 1)$很好轉(zhuǎn)移

然后跑莫隊即可

復(fù)雜度$O(N\sqrt{T})$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> #define MAXN 100005 #define MAX 100000 inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } const int MOD=1e9+7; using namespace std; typedef long long ll; inline int qpow(int a,int p) {int ans=1;while (p){if (p&1) ans=(ll)ans*a%MOD;a=(ll)a*a%MOD,p>>=1;}return ans; } int fac[MAXN],inv[MAXN]; void init() {fac[0]=1;for (int i=1;i<=MAX;i++) fac[i]=(ll)fac[i-1]*i%MOD;inv[MAX]=qpow(fac[MAX],MOD-2);for (int i=MAX-1;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%MOD; } inline int C(const int& n,const int& m){return (ll)fac[n]*inv[m]%MOD*inv[n-m]%MOD;} int len; struct query{int x,y,pos;}q[MAXN]; int res[MAXN]; inline bool operator <(const query& a,const query& b) {if (a.x/len==b.x/len) return a.y<b.y;return a.x<b.x; } int main() {init();int T,n=0;T=read();for (int i=1;i<=T;i++) n=max(n,q[i].x=read()),q[i].y=read(),q[i].pos=i;len=sqrt((ll)n*n/T);sort(q+1,q+T+1);int x=q[1].x,y=q[1].y,ans=0;for (int i=0;i<=y;i++) ans=(ans+C(x,i))%MOD;res[q[1].pos]=ans;for (int i=2;i<=T;i++){while (x<q[i].x) ans=(ans*2ll-C(x,y)+MOD)%MOD,++x;while (x>q[i].x) --x,ans=(ll)inv[2]*(ans+C(x,y))%MOD;while (y<q[i].y) ++y,ans=(ans+C(x,y))%MOD;while (y>q[i].y) ans=(ans+MOD-C(x,y))%MOD,--y;res[q[i].pos]=ans;}for (int i=1;i<=T;i++) printf("%d\n",(res[i]+MOD)%MOD);return 0; }

由此題可知，莫隊不只能處理區(qū)間，凡是方便相鄰轉(zhuǎn)移的函數(shù)都可以考慮莫隊

總結(jié)

以上是生活随笔為你收集整理的【AT987】高橋君【组合数】【莫队】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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