牛客网暑期ACM多校训练营第九场

study from : https://blog.csdn.net/mitsuha_/article/details/81774727

k较小。分离x和k。

另外的可能：求a[k][x]，x不确定，想到的是求sum(a[k][1]+a[k][2]+...+a[k][x])，树状数组 sum(x)-sum(x-1)。这题用不上。

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <set>
  8 #include <map>
  9 #include <queue>
 10 #include <iostream>
 11 using namespace std;
 12 
 13 #define ll long long
 14 
 15 const int maxn=1e5+10;
 16 const int maxk=40+1;
 17 const int inf=1e9;
 18 const ll mod=1e9+7;
 19 const double eps=1e-8;
 20 
 21 ll f[maxk][maxn],mul[maxn],chu[maxn];
 22 int n,k;
 23 
 24 ll C(int x,int y)
 25 {
 26     if (x<0)
 27     {
 28         x=y-1-x;
 29         return (y&1?-1:1)*mul[x]*chu[x-y]%mod*chu[y]%mod;
 30     }
 31     if (x<y)
 32         return 0;
 33     return mul[x]*chu[x-y]%mod*chu[y]%mod;
 34 }
 35 
 36 ll _pow(ll a,ll b)
 37 {
 38     ll y=1;
 39     while (b)
 40     {
 41         if (b &1)
 42             y=y*a%mod;
 43         a=a*a%mod;
 44         b>>=1;
 45     }
 46     return y;
 47 }
 48 
 49 void update(int x,ll y,int j)
 50 {
 51     while (x<=n)
 52     {
 53         f[j][x]=(f[j][x]+y)%mod;
 54         x+=x&-x;
 55     }
 56 }
 57 
 58 ll cal(int x,int j)
 59 {
 60     ll sum=0;
 61     while (x)
 62     {
 63         sum=(sum+f[j][x])%mod;
 64         x-=x&-x;
 65     }
 66     return sum;
 67 }
 68 
 69 int main()
 70 {
 71     int m,i,j,mode,x;
 72     ll sum=0,y;
 73     scanf("%d%d%d",&n,&m,&k);
 74     k--;
 75     mul[0]=1;
 76     for (i=1;i<=n;i++)
 77         mul[i]=mul[i-1]*i%mod;
 78     chu[n]=_pow(mul[n],mod-2);
 79     for (i=n-1;i>=0;i--)
 80         chu[i]=chu[i+1]*(i+1)%mod;
 81     while (m--)
 82     {
 83         scanf("%d",&mode);
 84         if (mode)
 85         {
 86             scanf("%d",&x);
 87             sum=0;
 88             for (j=0;j<=k;j++)
 89                 sum=(sum+C(x,j)*cal(x,j))%mod;
 90             printf("%lld
",sum);
 91         }
 92         else
 93         {
 94             scanf("%d%lld",&x,&y);
 95             for (j=0;j<=k;j++)
 96                 update(x,C(k-x,k-j)*y%mod,j);
 97         }
 98     }
 99     return 0;
100 }
101 /*
102 4 11 3
103 0 3 1
104 1 4
105 */

CGambling

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <set>
 8 #include <map>
 9 #include <queue>
10 #include <iostream>
11 using namespace std;
12 
13 #define ll long long
14 
15 const int maxn=1e5+10;
16 const int inf=1e9;
17 const double eps=1e-8;
18 const ll mod=1e9+7;
19 
20 ll mul[maxn<<1],chu[maxn<<1];
21 
22 ll _pow(ll a,ll b)
23 {
24     ll y=1;
25     while (b)
26     {
27         if (b&1)
28             y=y*a%mod;
29         a=a*a%mod;
30         b>>=1;
31     }
32     return y;
33 }
34 
35 ll C(ll x,ll y)
36 {
37     return mul[x]*chu[x-y]%mod*chu[y]%mod;
38 }
39 
40 int main()
41 {
42     int n,i,j,a;
43     scanf("%d",&n);
44     mul[0]=1;
45     for (i=1;i<=2*n;i++)
46         mul[i]=mul[i-1]*i%mod;
47     chu[2*n]=_pow(mul[2*n],mod-2);
48     for (i=2*n-1;i>=0;i--)
49         chu[i]=chu[i+1]*(i+1)%mod;
50     i=0,j=0;
51     while (~scanf("%d",&a))
52     {
53         printf("%lld
",_pow(2,1+i+j)*C(2*n-2-i-j,n-i-1)%mod);
54         i+=(a==0),j+=(a==1);
55     }
56     return 0;
57 }
58 /*
59 
60 */

GLongest Common Subsequence

牛客网暑期ACM多校训练营 第九场

牛客网暑期ACM多校训练营第九场