2016 Asia Jakarta Regional Contest J - Super Sum UVALive

J-Super Sum

题目大意就是给定N个三元组<a,b,c>求Σ（a1^k1*a2^k2*...*ai^ki*..an^kn)(bi<=ki<=ci)

唉。其实题目本身不难的，怪我不知道当时怎么想的。。。本来观察式子很容易能得出结论：

比如<5,2,3>,<2,1,4>,<3,2,2>这组：

　　5^2*2^1*3^2+5^2*2^2*3^2+5^2*2^3*3^2+5^2*2^4*^32=5^2*(2^1+2^2+2^3+2^4)*3^2;

　　5^3*2^1*3^2+5^3*2^2*3^2+5^3*2^3*3^2+5^3*2^4*^32=5^3*(2^1+2^2+2^3+2^4)*3^2;

　　=(5^2+5^3)*(2^1+2^2+2^3+2^4)*3^2;

很明显啊！就行对应三元组的等比数列相乘啊！

用组合的角度看也是啊，那几个式子不就相当于最后这个式子拆开再相加吗！

到这里基本就已经解决问题了。。。。。。。。。唯一需要注意的就是等比数列相乘时有除法，求模的时候要把分母转化成它的逆元。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int mod=1e9+;

 ll qpow(ll a,ll b)//快速幂

 {

     ll r=;

     while(b)

     {

         if(b&) r=r*a%mod;

         b>>=;

         a=a*a%mod;

     }

     return r;

 }

 ll inv(ll a)//费马小定理求逆元

 {

     return qpow(a,mod-);

 }

 int main()

 {

     int T;

     cin>>T;

     for (int cas=;cas<=T;cas++)

     {

         int n;

         cin>>n;

         ll ans=;

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

         {

             ll a,b,c;

             cin>>a>>b>>c;

             if(a==){//公比为1单独处理

                 ans=(ans%mod*(c-b+)%mod)%mod;

             }

             else

             {

                 ans=(ans%mod*(qpow(a,b)%mod*(qpow(a,c-b+)-)%mod*inv(a-)%mod)%mod)%mod;

             }

         }

         cout<<"Case #"<<cas<<": ";

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

2016 Asia Jakarta Regional Contest J - Super Sum UVALive - 7720 【快速幂+逆元】

最新文章

热门文章