建立 wiki 网站,齐河网站建设费用,创建,网页设计与制作教程考试题目传送门
题意#xff1a;TTT组询问NNN个相同物品选不超过KKK个的方案数#xff0c;T,N≤1e5T,N \leq 1e5T,N≤1e5
设f(x,y)∑i0yCxif(x,y)\sum_{i0}^{y}C_x^if(x,y)∑i0yCxi即所求
直接求并没有很好的性质
但我们发现:f(x,y)2f(x−1,y)−Cx−1yf(x,y)2f(x-1,y)-C_{x-1…传送门
题意TTT组询问NNN个相同物品选不超过KKK个的方案数T,N≤1e5T,N \leq 1e5T,N≤1e5
设f(x,y)∑i0yCxif(x,y)\sum_{i0}^{y}C_x^if(x,y)∑i0yCxi即所求
直接求并没有很好的性质
但我们发现:f(x,y)2f(x−1,y)−Cx−1yf(x,y)2f(x-1,y)-C_{x-1}^yf(x,y)2f(x−1,y)−Cx−1y即乘以二减去最后一个等于下一行
由CnmCn−1mCn−1m−1C_n^mC_{n-1}^mC_{n-1}^{m-1}CnmCn−1mCn−1m−1,只有最后一个出现一次其余出现两次
而f(x,y)到f(x,y)到f(x,y)到f(x,y±1)f(x,y \pm 1)f(x,y±1)很好转移
然后跑莫队即可
复杂度O(NT)O(N \sqrt{T})O(NT) #include iostream
#include cstdio
#include cstring
#include cctype
#include cmath
#include algorithm
#define MAXN 100005
#define MAX 100000
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
const int MOD1e97;
using namespace std;
typedef long long ll;
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD,p1;}return ans;
}
int fac[MAXN],inv[MAXN];
void init()
{fac[0]1;for (int i1;iMAX;i) fac[i](ll)fac[i-1]*i%MOD;inv[MAX]qpow(fac[MAX],MOD-2);for (int iMAX-1;i0;i--) inv[i](ll)inv[i1]*(i1)%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/lenb.x/len) return a.yb.y;return a.xb.x;
}
int main()
{init();int T,n0;Tread();for (int i1;iT;i) nmax(n,q[i].xread()),q[i].yread(),q[i].posi;lensqrt((ll)n*n/T);sort(q1,qT1);int xq[1].x,yq[1].y,ans0;for (int i0;iy;i) ans(ansC(x,i))%MOD;res[q[1].pos]ans;for (int i2;iT;i){while (xq[i].x) ans(ans*2ll-C(x,y)MOD)%MOD,x;while (xq[i].x) --x,ans(ll)inv[2]*(ansC(x,y))%MOD;while (yq[i].y) y,ans(ansC(x,y))%MOD;while (yq[i].y) ans(ansMOD-C(x,y))%MOD,--y;res[q[i].pos]ans;}for (int i1;iT;i) printf(%d\n,(res[i]MOD)%MOD);return 0;
}由此题可知莫队不只能处理区间凡是方便相邻转移的函数都可以考虑莫队
