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

时间：2024-04-24 17:19:18

HPrefix Sum

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

k较小。分离x和k。

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

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

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

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

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <iostream>

 using namespace std;

 #define ll long long

 const int maxn=1e5+;

 const int maxk=+;

 const int inf=1e9;

 const ll mod=1e9+;

 const double eps=1e-;

 ll f[maxk][maxn],mul[maxn],chu[maxn];

 int n,k;

 ll C(int x,int y)

 {

     if (x<)

     {

         x=y--x;

         return (y&?-:)*mul[x]*chu[x-y]%mod*chu[y]%mod;

     }

     if (x<y)

         return ;

     return mul[x]*chu[x-y]%mod*chu[y]%mod;

 }

 ll _pow(ll a,ll b)

 {

     ll y=;

     while (b)

     {

         if (b &)

             y=y*a%mod;

         a=a*a%mod;

         b>>=;

     }

     return y;

 }

 void update(int x,ll y,int j)

 {

     while (x<=n)

     {

         f[j][x]=(f[j][x]+y)%mod;

         x+=x&-x;

     }

 }

 ll cal(int x,int j)

 {

     ll sum=;

     while (x)

     {

         sum=(sum+f[j][x])%mod;

         x-=x&-x;

     }

     return sum;

 }

 int main()

 {

     int m,i,j,mode,x;

     ll sum=,y;

     scanf("%d%d%d",&n,&m,&k);

     k--;

     mul[]=;

     for (i=;i<=n;i++)

         mul[i]=mul[i-]*i%mod;

     chu[n]=_pow(mul[n],mod-);

     for (i=n-;i>=;i--)

         chu[i]=chu[i+]*(i+)%mod;

     while (m--)

     {

         scanf("%d",&mode);

         if (mode)

         {

             scanf("%d",&x);

             sum=;

             for (j=;j<=k;j++)

                 sum=(sum+C(x,j)*cal(x,j))%mod;

             printf("%lld\n",sum);

         }

         else

         {

             scanf("%d%lld",&x,&y);

             for (j=;j<=k;j++)

                 update(x,C(k-x,k-j)*y%mod,j);

         }

     }

     return ;

 }

 /*

 4 11 3

 0 3 1

 1 4

 */

CGambling

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <iostream>

 using namespace std;

 #define ll long long

 const int maxn=1e5+;

 const int inf=1e9;

 const double eps=1e-;

 const ll mod=1e9+;

 ll mul[maxn<<],chu[maxn<<];

 ll _pow(ll a,ll b)

 {

     ll y=;

     while (b)

     {

         if (b&)

             y=y*a%mod;

         a=a*a%mod;

         b>>=;

     }

     return y;

 }

 ll C(ll x,ll y)

 {

     return mul[x]*chu[x-y]%mod*chu[y]%mod;

 }

 int main()

 {

     int n,i,j,a;

     scanf("%d",&n);

     mul[]=;

     for (i=;i<=*n;i++)

         mul[i]=mul[i-]*i%mod;

     chu[*n]=_pow(mul[*n],mod-);

     for (i=*n-;i>=;i--)

         chu[i]=chu[i+]*(i+)%mod;

     i=,j=;

     while (~scanf("%d",&a))

     {

         printf("%lld\n",_pow(,+i+j)*C(*n--i-j,n-i-)%mod);

         i+=(a==),j+=(a==);

     }

     return ;

 }

 /*

 */

GLongest Common Subsequence

相关文章