t2+t3+t4

t2: Tree IV

1. 同一层的坐标 要相乘的 层数 都是一样，所以同层的坐标可以用等差数列求和
2. 注意取模的问题，特别是除法 a/b%mod!=(a%mod)/(b%mod)%mod ，除法要用到逆元，这题范围没那么大，所以可以求完除法再取模

   typedef long long ll;
   class Solution {
    ll mod=998244353;
   public:
    long long tree4(long long n) {
        ll ans=0;
        ll level=1;
        ll num=1;
        ll st=1,ed=1;
        while (n>0)
        {
            ans+=sum(st,ed)*level%mod;
            ans%=mod;
            n-=num;
            ++level;
            num*=2;
            st*=2;
            ed=min(ed*2+1,st+n-1);
        }
        return ans;
    }
    ll sum(ll a,ll b)
    {
        ll n=b-a+1;
        return n*(a+b)/2%mod;
    }
   };

t3:牛牛组数

1. 显然是贪心，位数越长越有利
2. 所以先对题目给的字符串按照逆序排列，且第一个取的串尽可能的长，让剩下的k-1个数字都只有一个字符
3. 剩下就是字符串相加了，但是字符串相加很慢，一个优化就是，既然剩下k-1个数字都是一个字符，即都是单个数字，可以先求和这k-1个数字
4. 最后只用一次字符串相加：第一个贪心得来的超长的字符串 + 剩下k-1个数字的和后的字符串

class Solution {
public:
    string Maxsumforknumers(string x, int k) {
        sort(x.rbegin(),x.rend());
        if (k==1)
            return x;
        int x_size=x.size();
        if (k==x_size)
        {
            int ans=0;
            for (char i:x)
                ans+=i-'0';
            return to_string(ans);
        }
        string num1=x.substr(0,x_size-k+1);
        int n2=0;
        for (int idx=x_size-k+1;idx<x_size;++idx)
            n2+=x.at(idx)-'0';
        string num2=to_string(n2);
        string ans;
        int i=num1.size()-1,j=num2.size()-1;
        int sum;
        int num1_i,num2_j;
        int carry=0;
        while (i>=0 || j>=0)
        {
            num1_i= i>=0 ? num1.at(i)-'0' : 0;
            num2_j= j>=0 ? num2.at(j)-'0' : 0;
            sum=carry+num1_i+num2_j;
            ans+=(sum%10+'0');
            carry=sum/10;
            --i;
            --j;
        }
        if (carry==1)
            ans+='1';
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

t4.牛牛算题

1. 旭日东升BJFU的题解里的这个图很强

2. 剩下一个整数分块
3. 然后再用到等差数列求和

typedef long long ll;
/*
 * n=p*k+m 求p从1~n，所有的k*m求和
 * 即 sum((n/p) * (n%p))
 * 即 sum((n/p) * (n-n/p*p))
 * 整数分块，即在一定区间内n/p都是一个值，根据结果反推p的取值范围
 * int(num/i)=C
   i在[l,r]的一个区间，只需要知道l
   C=num/l
   r=num/(num/l)
 * 递归下去就是l=r+1
 */
class Solution {
    ll mod=1e9+7;
public:
    long long cowModCount(long long num) {
        ll ans=0;
        ll l=1,r,C;
        while (l<num)
        {
            r=num/(num/l);
            C=num/l;
            ll cnt=r-l+1;
            ll sum_p=sum(l,r);
            ans+=C*(cnt*num%mod-C*sum_p%mod+mod)%mod;
            ans%=mod;
            l=r+1;
        }
        return ans;
    }
    ll sum(ll a,ll b)
    {
        ll n=b-a+1;
        return n*(a+b)/2%mod;
    }
};