牛客练习赛42D（性质、数学）

就像题解所说的，写几个可以发现有分成四段的性质：第一段是从n开始往下贪，第二段是个数字，第三段……卧槽好吧真难描述。

然后发现这个数据量可达1e9，所以考虑“二分确定序列+数学计算”的方式解题。

首先二分出第一段的长度，这里我写得丑了，又将某些情况特判了一下；不难发现有了第一段的长度、N、K这三个量，序列已确定。

然后疯狂手推数学公式把这四段的值求出来，特殊情况的例子很好举，自己调一调打打补丁做一做膜法，大概就莽A了吧……不过要是在考场上本垃圾就必死无疑了。

 #include <cstdio>

 #include <cmath>

 #include <iostream>

 using namespace std;

 typedef long long ll;

 const ll mod = 1e9 + ;

 ll N, K, x, ans1, ans2, ans3, ans4;

 ll add(ll a, ll b) {

     return a + b >= mod ? a + b - mod : a + b;

 }

 ll sub(ll a, ll b) {

     return a - b <  ? a - b + mod : a - b;

 }

 ll ksm(ll a, ll b) {

     ll ret = ;

     for (; b; b >>= ) {

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

         a = a * a % mod;

     }

     return ret;

 }

 inline ll cal(ll l, ll r) {

     return (l + r) * (r - l + ) / ;

 }

 inline ll cal2(ll n) {//这是求x + 2*x^2 + ... + n*x^n的函数

     ll a = n % mod * ksm(x, n + ) % mod * (x - ) % mod;

     ll b = x * sub(ksm(x, n), ) % mod;

     return sub(a, b) * ksm((x - ) * (x - ) % mod, mod - ) % mod;

 }

 int main() {

     cin >> N >> K;

     x = N + ;

     if (K == ) {

         cout << cal2(N) << endl;

         return ;

     }

     ll l = , r = N;

     while (l < r) {

         ll mid = (l + r) >> ;

         if (cal(N - mid, N - ) <= K)    l = mid + ;

         else    r = mid;

     }

     while (cal(N - l, N - ) >= K)    l--;//至此l为第一段长度。如果出现54312这种，会将54作为第一段，3作为第二段，12为第三段，第四段为空

     if (l) {

         ans1 = add(sub(x * x % mod * (ksm(x, l) -  + mod) % mod * ksm(x - , mod - ) % mod, l * x % mod), (N - l) * x % mod * (ksm(x, l) -  + mod) % mod) * ksm(x - , mod - ) % mod;

         K -= cal(N - l, N - );

     }

     if (K) {

         K++, l++;//K就是第二段那个数字，l++只是为了运算简便

         ans2 = K % mod * ksm(x, l) % mod;

         ans3 = ksm(x, l) * cal2(K - ) % mod;

         if (N - l +  > K) {//如果有第四段

             ll tmp = K % mod * sub(ksm(x, N + ), ksm(x, K + l)) % mod * ksm(x - , mod - ) % mod;

             ans4 = add(tmp, ksm(x, K + l - ) * cal2(N - K - l + ) % mod);

         }

     }

     cout << (ans1 + ans2 + ans3 + ans4) % mod;

     return ;

 }

巴特西

牛客练习赛42D（性质、数学）

最新文章

热门文章