Problem B. Harvest of Apples 莫队求组合数前缀和-白红宇

Problem B. Harvest of Apples 莫队求组合数前缀和

阅读量：4986 次

发布时间：2019-06-12

本文共 2906 字，大约阅读时间需要 9 分钟。

Problem Description

There are

Input

The first line of the input contains an integer

Output

For each test case, print an integer representing the number of ways modulo

Sample Input

2 5 2 1000 500

Sample Output

16 924129523

Source

Recommend

这题刚写的时候公式及其的容易推 C(n,0)+C(n,1)+C(n,2)+。。。+C(n,m)

然后一直在想能不能化简这一项一项的求复杂度会爆炸的

最后的题解是莫队

C(n,m)=C(n-1,m-1)+C(n-1,m)

设 S(n,m)=C(n,0)+C(n,1)+C(n,2)+。。。+C(n,m)

然后将S(n,m) 通过第一个公式拆项

最后化简变为 S(n,m)=2*S(n-1,m)-C(n-1,m);

预处理阶乘逆元然后就 OK了

莫队大法好

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #define pi acos(-1.0)13 #define eps 1e-614 #define fi first15 #define se second16 #define lson l,m,rt<<117 #define rson m+1,r,rt<<1|118 #define bug printf("******\n")19 #define mem(a,b) memset(a,b,sizeof(a))20 #define fuck(x) cout<<"["<
                 
                  <<"]"<
                  
                   = b; i--)29 #define FRL(i,a,b) for(i = a; i < b; i++)30 #define FRLL(i,a,b) for(i = a; i > b; i--)31 #define FIN freopen("DATA.txt","r",stdin)32 #define gcd(a,b) __gcd(a,b)33 #define lowbit(x) x&-x34 #pragma comment (linker,"/STACK:102400000,102400000")35 using namespace std;36 typedef long long LL;37 typedef unsigned long long ULL;38 const int INF = 0x7fffffff;39 const int mod = 1e9 + 7;40 const int maxn = 1e5 + 10;41 int t, sz;42 LL inv[maxn], a[maxn], b[maxn];43 struct node {44 int l, r, id;45 LL ans = 0;46 } qu[maxn];47 int cmp(node a, node b) {48 return a.l / sz == b.l / sz ? a.r < b.r : a.l < b.l;49 }50 LL expmod(LL a, LL b) {51 LL ans = 1;52 while(b) {53 if (b & 1) ans = ans * a % mod;54 a = a * a % mod;55 b = b >> 1;56 }57 return ans;58 }59 void init() {60 a[1] = 1;61 for (int i = 2 ; i < maxn ; i++) a[i] = a[i - 1] * i % mod;62 for (int i = 1 ; i < maxn ; i++) b[i] = expmod(a[i], mod - 2);63 }64 LL C(int n, int m) {65 if (m > n || n < 0 || m < 0 ) return 0;66 if (m == n || m == 0) return 1;67 return a[n] * b[m] % mod * b[n - m] % mod;68 }69 70 int main() {71 init();72 sf(t);73 for (int i = 1 ; i <= t ; i++) {74 sff(qu[i].l, qu[i].r);75 qu[i].id = i, qu[i].ans = 0;76 }77 sz = sqrt(maxn);78 sort(qu + 1, qu + 1 + t, cmp);79 LL sum = 1;80 for (int i = 1, L = 1, R = 0 ; i <= t ; i++) {81 while(L < qu[i].l) sum = (2 * sum - C(L++, R) + mod) % mod;82 while(L > qu[i].l) sum = ((sum + C(--L, R)) * b[2]) % mod;83 while(R < qu[i].r) sum = (sum + C(L, ++R)) % mod;84 while(R > qu[i].r) sum = (sum - C(L, R--) + mod) % mod;85 qu[qu[i].id].ans = sum;86 }87 for (int i = 1 ; i <= t ; i++) printf("%lld\n", qu[i].ans);88 return 0;89 }