1 条题解

  • 13
    @ 2024-10-4 12:44:48

    这道题我们可以简单打个表:

    n\m 11 22 33 44
    11 1 2 3 4
    22 2 4 6 8
    33 3 6 9 12
    44 4 8 12 16

    由此可得

    原式

    =(m+1)m2+(2m+2)m2+....+(nm+n)m2=\dfrac{(m+1)m}{2}+\dfrac{(2m+2)m}{2}+....+\dfrac{(nm+n)m}{2}

    =(1+2+....+n)m2+m2=(1+2+....+n)\dfrac{m^2+m}{2}

    =n2+n2×m2+m2=\dfrac{n^2+n}{2} \times \dfrac{m^2+m}{2}

    =(n2+n)(m2+m)4=\dfrac{(n^2+n)(m^2+m)}{4}

    这个分数的上半部分直接取模即可,但是下面的 ×14\times \dfrac{1}{4} 需要取它的乘法逆元,也就是 (4p2)modp(4^{p-2}) \bmod p

    代码

    #include<bits/stdc++.h>
    using namespace std;
    const long long mod=1e9+7;
    long long m,n,zancun1,zancun2,ans;
    long long qpow(long long a,long long b,long long mod){
       long long ans=1;
       while(b){
          if(b&1) ans=(ans*a)%mod;
          b>>=1;
          a=(a*a)%mod;
       }
       return ans;
    }
    int main(){
       //freopen("falcon.in","r",stdin);
       //freopen("falcon.out","w",stdout);
       cin>>n>>m;
       zancun1=(((n%mod)*(n%mod))%mod+(n%mod))%mod;
       zancun2=(((m%mod)*(m%mod))%mod+(m%mod))%mod;
       ans=(((zancun1*zancun2)%mod)*qpow(4,1000000005,mod))%mod;
       cout<<ans;
       return 0;
    }
    
  • 1

信息

ID
779
时间
1000ms
内存
256MiB
难度
8
标签
(无)
递交数
105
已通过
19
上传者