NC579 题解 | #牛牛的函数2#

题意分析

• 定义函数 ，然后在给定a和b的情况下，求的值。

  思路分析

• 这个题目就是NC578的加强版。这个题目就是一个公式的推导。

• 这就是数学，一个很复杂的公式推导出了一个简洁的式子。另外，我们发现，这个式子的数据范围过大，可能存在爆long long的写法。所以这里我们使用int128实现。

写法一 迭代法

• 代码如下
  • 快速幂和快速乘的写法是log级别的。所以总的时间复杂度是
  • 过程中基本没有开其余变量，空间复杂度为

class Solution {
public:
    /**
     * 
     * @param sa string字符串 
     * @param sb string字符串 
     * @param n int整型 
     * @return long长整型
     */
    // 这里用int128实现
    typedef __int128 ll;
    const ll mod = 10000000033;
    // 快速乘写法
    ll qc(ll a,ll b){
        ll c=0;
        while(b){
            if(b&1) c=(c+a)%mod;
            b>>=1;
            // 如果指数为偶数的请款，那么进行迭代处理
            a=(a+a)%mod;
        }
        return c;
    }
    // 快速幂的写法
    ll qp(ll a,ll b){
        ll c=1;
        while(b){
            if(b&1) c=qc(c,a)%mod;
            b>>=1;
            // 如果指数偶数的情况，那么递归处理
            a=qc(a,a)%mod;
        }
        return c;
    }
    // 获取字符串对应的具体的数字
    ll getnum(string s){
        ll sum=0;
        for(auto x:s){
            sum=sum*10+(ll)(x-'0');
        }
        return sum;
    }
    long long solve(string sa, string sb, int n) {
        // write code here
        ll a=getnum(sa);
       // a=(a%mod+mod)%mod;
        ll b=getnum(sb);
       // b=(b%mod+mod)%mod; 
       // 特判等号的情况
        if(n==0){
            return 0;
        }else if(n==1){
            // 特判为1的情况
            ll tmp1=qc(b,b+1)-qc(a,a+1);
            tmp1=(tmp1+mod)%mod;
            ll down=qp(2,mod-2);
            ll ans=qc(tmp1,down);
            return ans;
        }
        ll down=qp(n-1,mod-2);
        ll tmp1=qc(b,qp(n,b));
        ll tmp2=qc(a,qp(n,a));
        ll tmp3=qp(n,b)-qp(n,a);
        tmp3=(tmp3%mod+mod)%mod;
        tmp3=qc(tmp3,down);
        ll tmp=((tmp1-tmp2-tmp3)%mod+mod)%mod;
        ll ans=qc(tmp,down);
        return ans;
    }
};

写法二 递归

• 其实在迭代的过程中我们可以使用递归的写法进行代替，这样可能更好理解一点。
• 代码如下
  • 快速幂和快速乘的写法是log级别的。所以总的时间复杂度是
  • 过程中基本没有开其余变量，空间复杂度为

class Solution {
public:
    /**
     * 
     * @param sa string字符串 
     * @param sb string字符串 
     * @param n int整型 
     * @return long长整型
     */
    // 这里用int128实现
    typedef __int128 ll;
    const ll mod = 10000000033;
    // 快速乘写法
    ll qc(ll a,ll b){
        if(b==0) return 0;
        if(b&1) return (a+qc(a,b-1))%mod;
        else{
            ll tmp=qc(a,b/2);
            // 如果是偶数的情况，那么进行迭代处理
            return (tmp+tmp)%mod;
        }
    }
    // 快速幂的写法
    ll qp(ll a,ll b){
        if(b==0) return 1;
        if(b&1) return qc(a,qp(a,b-1));
        else{
            ll tmp=qp(a,b/2);
            // 如果是偶数的情况，那么进行递归处理
            return qc(tmp,tmp);
        }
    }
    // 获取字符串对应的具体的数字
    ll getnum(string s){
        ll sum=0;
        for(auto x:s){
            sum=sum*10+(ll)(x-'0');
        }
        return sum;
    }
    long long solve(string sa, string sb, int n) {
        // write code here
        ll a=getnum(sa);
       // a=(a%mod+mod)%mod;
        ll b=getnum(sb);
       // b=(b%mod+mod)%mod;
        if(n==0){
            return 0;
        }else if(n==1){
            ll tmp1=qc(b,b+1)-qc(a,a+1);
            tmp1=(tmp1+mod)%mod;
            ll down=qp(2,mod-2);
            ll ans=qc(tmp1,down);
            return ans;
        }
        ll down=qp(n-1,mod-2);
        ll tmp1=qc(b,qp(n,b));
        ll tmp2=qc(a,qp(n,a));
        ll tmp3=qp(n,b)-qp(n,a);
        tmp3=(tmp3%mod+mod)%mod;
        tmp3=qc(tmp3,down);
        ll tmp=((tmp1-tmp2-tmp3)%mod+mod)%mod;
        ll ans=qc(tmp,down);
        return ans;
    }
};