2018 Multi-University Training Contest 4 Problem B. Harvest of Apples 【莫队+排列组合+逆元预处理技巧】...

任意门：http://acm.hdu.edu.cn/showproblem.php?pid=6333

Problem B. Harvest of Apples

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 4043    Accepted Submission(s): 1560

题意概括：

有 N 个苹果，问最多选 m 个苹果的方案有多少种？

解题思路：

大佬讲的很好了。

https://blog.csdn.net/codeswarrior/article/details/81359075

推出四个公式，算是一道比较裸的莫队了。

Sm−1n=Smn−CmnSnm−1=Snm−Cnm
Sm+1n=Smn+Cm+1nSnm+1=Snm+Cnm+1(或者Smn=Sm−1n+CmnSnm=Snm−1+Cnm)

Smn+1=2Smn−CmnSn+1m=2Snm−Cnm
Smn−1=Smn+Cmn−12Sn−1m=Snm+Cn−1m2(或者Smn=Smn+1+Cmn2Snm=Sn+1m+Cnm2)

需要注意的点较多：

1、精度问题，注意数据范围

2、为了保证精度，除法需要转换为逆元，预处理逆元的技巧

AC code:

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include
  8 #include<set>
  9 #define INF 0x3f3f3f3f
 10 #define LL long long
 11 using namespace std;
 12 const LL MOD = 1e9+7;
 13 const int MAXN = 1e5+10;
 14 LL N, M;
 15 LL fac[MAXN], inv[MAXN];
 16 struct Query
 17 {
 18     int L, R, id, block;
 19     bool operator < (const Query &p)const{
 20         if(block == p.block) return R < p.R;
 21         return block < p.block;
 22     }
 23 }Q[MAXN];
 24 LL res, rev2;
 25 LL ans[MAXN];
 26 
 27 LL q_pow(LL a, LL b)
 28 {
 29     LL pans = 1LL;
 30     while(b){
 31         if(b&1) pans = pans*a%MOD;
 32         b>>=1LL;
 33         a = a*a%MOD;
 34     }
 35     return pans;
 36 }
 37 
 38 LL C(int n, int k)
 39 {
 40     return fac[n]*inv[k]%MOD*inv[n-k]%MOD;
 41 }
 42 
 43 void init()
 44 {
 45     rev2 = q_pow(2, MOD-2);                     // 2的逆元
 46     fac[0] = fac[1] = 1;
 47     for(LL i = 2; i < MAXN; i++){              //预处理阶乘
 48         fac[i] = fac[i-1]*i%MOD;
 49     }
 50 
 51     inv[MAXN-1] = q_pow(fac[MAXN-1], MOD-2);    //逆推预处理阶乘的逆元
 52     for(int i = MAXN-2; i >= 0; i--){
 53         inv[i] = inv[i+1]*(i+1)%MOD;
 54     }
 55 }
 56 
 57 void  addN(int posL, int posR)
 58 {
 59     res = (2*res%MOD-C(posL-1, posR)%MOD + MOD)%MOD;
 60 }
 61 
 62 void addM(int posL, int posR)
 63 {
 64     res = (res+C(posL, posR))%MOD;
 65 }
 66 
 67 void delN(int posL, int posR)
 68 {
 69     res = (res+C(posL-1, posR))%MOD*rev2%MOD;
 70 }
 71 
 72 void delM(int posL, int posR)
 73 {
 74     res = (res - C(posL, posR) + MOD)%MOD;
 75 }
 76 
 77 int main()
 78 {
 79     int T_case;
 80     init();
 81     int len = (int)sqrt(MAXN*1.0);
 82     scanf("%d", &T_case);
 83     for(int i = 1; i <= T_case; i++){
 84         scanf("%d%d", &Q[i].L, &Q[i].R);
 85         Q[i].id = i;
 86         Q[i].block = Q[i].L/len;
 87     }
 88     sort(Q+1, Q+1+T_case);
 89     res = 2;
 90     int curL = 1, curR = 1;
 91     for(int i = 1; i <= T_case; i++){
 92         while(curL < Q[i].L) addN(++curL, curR);
 93         while(curR < Q[i].R) addM(curL, ++curR);
 94         while(curL > Q[i].L) delN(curL--, curR);
 95         while(curR > Q[i].R) delM(curL, curR--);
 96         ans[Q[i].id] = res;
 97     }
 98     for(int i = 1; i <= T_case; i++){
 99         printf("%lld\n", ans[i]);
100     }
101 
102     return 0;
103 
104 }

转载于:https://www.cnblogs.com/ymzjj/p/10330540.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！