【牛客小白月赛6】 J 洋灰三角 - 快速幂&逆元&数学

题目地址：https://www.nowcoder.com/acm/contest/136/J

解法一：

　　推数学公式求前n项和；　

　　当k=1时，即为等差数列，S= n+pn(n−1)/2
　　当k≠1时，a+p/(k−1) = k(a+p/(k-1))，等比数列，S= (k+(p−1)k−(np+1)k+(n−1)p+1) / ((k-1)*(k-1))

　　因为是除法取模，故除快速幂外还需逆元；

Knowledge Point：

　　除法取模逆元：https://www.cnblogs.com/ECJTUACM-873284962/p/6847672.html

　　费马小定理：若p是质数，且a、p互质，那么a^(p-1) mod p = 1。

 #include<iostream>

 using namespace std;

 #define LL long long

 const LL MOD = 1e9+;

 LL n,k,p;

 LL pow(LL a, LL x)

 {

     LL tmp=;

     while(x) {

         if(x&)

             tmp = tmp*a%MOD;

         a = a*a%MOD;

         x>>=;

     }

     return tmp;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     while(cin>>n>>k>>p)

     {

         if(k == )

             cout<<(n+p*n*(n-)/)%MOD<<endl;

         else {

             LL t = pow(k,n);

             LL ans = t*k+(p-)*t-k*(n*p+)+(n-)*p+;

             ans = (ans%MOD+MOD)%MOD;

             ans = ans*pow((k-)*(k-), MOD-)%MOD;

             cout<<ans<<endl;

         }

     }

     return ;

 }

解法二：

　　杜教板子：https://www.cnblogs.com/liubilan/p/9520292.html

　　直接套杜教板子；

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <map>

 #include <set>

 #include <cassert>

 #include<bits/stdc++.h>

 #define rep(i,a,n) for (ll  i=a;i<n;i++)

 #define per(i,a,n) for (ll  i=n-1;i>=a;i--)

 #define pb push_back

 #define mp make_pair

 #define all(x) (x).begin(),(x).end()

 #define fi first

 #define se second

 #define SZ(x) ((ll )(x).size())

 using namespace std;

 typedef long long ll;

 typedef vector<ll > VI;

 typedef pair<ll ,ll > PII;

 const ll mod=;

 ll powmod(ll a,ll b) {ll res=;a%=mod; assert(b>=); for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}

 // head

 ll  _,n;

 namespace linear_seq {

     const ll  N=;

     ll res[N],base[N],_c[N],_md[N];

     vector<ll > Md;

     void mul(ll *a,ll *b,ll  k) {

         rep(i,,k+k) _c[i]=;

         rep(i,,k) if (a[i]) rep(j,,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;

         for (ll  i=k+k-;i>=k;i--) if (_c[i])

             rep(j,,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;

         rep(i,,k) a[i]=_c[i];

     }

     ll  solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...

 //        prll f("%d\n",SZ(b));

         ll ans=,pnt=;

         ll  k=SZ(a);

         assert(SZ(a)==SZ(b));

         rep(i,,k) _md[k--i]=-a[i];_md[k]=;

         Md.clear();

         rep(i,,k) if (_md[i]!=) Md.push_back(i);

         rep(i,,k) res[i]=base[i]=;

         res[]=;

         while ((1ll<<pnt)<=n) pnt++;

         for (ll  p=pnt;p>=;p--) {

             mul(res,res,k);

             if ((n>>p)&) {

                 for (ll  i=k-;i>=;i--) res[i+]=res[i];res[]=;

                 rep(j,,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;

             }

         }

         rep(i,,k) ans=(ans+res[i]*b[i])%mod;

         if (ans<) ans+=mod;

         return ans;

     }

     VI BM(VI s) {

         VI C(,),B(,);

         ll  L=,m=,b=;

         rep(n,,SZ(s)) {

             ll d=;

             rep(i,,L+) d=(d+(ll)C[i]*s[n-i])%mod;

             if (d==) ++m;

             else if (*L<=n) {

                 VI T=C;

                 ll c=mod-d*powmod(b,mod-)%mod;

                 while (SZ(C)<SZ(B)+m) C.pb();

                 rep(i,,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;

                 L=n+-L; B=T; b=d; m=;

             } else {

                 ll c=mod-d*powmod(b,mod-)%mod;

                 while (SZ(C)<SZ(B)+m) C.pb();

                 rep(i,,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;

                 ++m;

             }

         }

         return C;

     }

     ll  gao(VI a,ll n) {

         VI c=BM(a);

         c.erase(c.begin());

         rep(i,,SZ(c)) c[i]=(mod-c[i])%mod;

         return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));

     }

 };

 int  main() {

     ll   n, k, p;

     cin>>n>>k>>p;

     ll  sum[];

     ///求出前10项

     sum[]=;

     for(ll  i=;i<=;i++){

         sum[i]=(sum[i-]*k%mod+p)%mod;

     }

     for(ll  i=;i<=;i++){

         sum[i]=(sum[i-]+sum[i])%mod;

     }

     vector<ll >v;

     for(ll  i=;i<=;i++){

         v.push_back(sum[i]);

     }

     printf("%lld\n",linear_seq::gao(v,n-));

 }