fork download 
  1. #include <bits/stdc++.h>                    
  2. #define int long long    
  3. using namespace std;
  4. const long long N=2000005, mod=1000000007;
  5.  
  6. int power(int a, int b, int p)
  7. {
  8.     if(a==0)
  9.     return 0;
  10.     int res=1;
  11.     a%=p;
  12.     while(b>0)
  13.     {
  14.         if(b&1)
  15.         res=(1ll*res*a)%p;
  16.         b>>=1;
  17.         a=(1ll*a*a)%p;
  18.     }
  19.     return res;
  20. }
  21.  
  22. int pref[N], inv[N], pref2[N], hp2[N];
  23.  
  24. // Returns (1/l + 1/(l+1) + ... + 1/r)
  25. int cal(int l, int r)
  26. {
  27.     if(l>r)
  28.         return 0;
  29.     return (pref[r]-pref[l-1]+mod)%mod;
  30. }
  31.  
  32. // Returns (1/(l*(l+1)) + ... + 1/(r(r+1)))
  33. int cal2(int l, int r)
  34. {
  35.     if(l>r)
  36.         return 0;
  37.     return (pref2[r]-pref2[l-1]+mod)%mod;
  38. }
  39. void pre()
  40. {
  41.     pref[0]=0;
  42.     pref2[0]=0;
  43.     for(int i=1;i<N;i++)
  44.     {
  45.         inv[i]=power(i, mod-2, mod);
  46.         pref[i]=(pref[i-1]+inv[i])%mod;
  47.         int mul2=(i*(i+1))%mod;
  48.         pref2[i]=(pref2[i-1] + power(mul2, mod-2, mod))%mod;
  49.         hp2[i]=((i*(i-1))%mod)%mod;
  50.     }
  51. }
  52. int solve2(int n, int m, int k)
  53. {
  54.     if((n*m)<k)
  55.         return 0;
  56.     int ans=0;
  57.     int reqv=(k-1)/n;
  58.     if(reqv<m)
  59.     {
  60.         int prob=(reqv*inv[reqv+n-1])%mod;
  61.         int exp=(prob*(1ll + cal(n+reqv, m+n-2)))%mod;
  62.         ans=(ans + exp)%mod;
  63.     }
  64.     int reqh=(k-1)/m;
  65.     if(reqh<n)
  66.     {
  67.         int prob=(reqh*inv[reqh+m-1])%mod;
  68.         int exp=(prob*(1ll + cal(m+reqh, m+n-2)))%mod;
  69.         ans=(ans + exp)%mod;
  70.     }
  71.     for(int i=1;i<min(n, k);i++)
  72.     {
  73.         reqv=(k-1)/i;
  74.         if(reqv>=m)
  75.             continue;
  76.         int prob=(inv[i+reqv]*reqv)%mod;
  77.         prob=(prob*inv[i-1+reqv])%mod;
  78.         int num1=(hp2[i+reqv+1]*cal2(i+reqv, i+m-2))%mod;
  79.         int num2=((i+reqv+1)*cal(i+reqv+1, i+m-1))%mod;
  80.         int num=((num1+num2)*inv[i+reqv+1])%mod;
  81.         int exp=(prob*(2ll + cal(i+reqv+1, reqv+(n-1))+num))%mod;
  82.         ans=(ans + exp)%mod;
  83.     }
  84.     for(int i=1;i<min(m, k);i++)
  85.     {
  86.         reqh=(k-1)/i;
  87.         if(reqh>=n)
  88.             continue;
  89.         int prob=(inv[i+reqh]*reqh)%mod;
  90.         prob=(prob*inv[i-1+reqh])%mod;
  91.         // Sum for cases when the (reqh+i)th horizontal line comes in the gap b/w x_v and y1_h
  92.         int num1=(hp2[i+reqh+1]*cal2(i+reqh, i+n-2))%mod;
  93.         // Sum for cases when the (reqh+i)th horizontal line comes in the gap to the left of x_v
  94.         int num2=((i+reqh+1)*cal(i+reqh+1, i+n-1))%mod;
  95.         int num=((num1+num2)*inv[i+reqh+1])%mod;
  96.         int exp=(prob*(2ll + cal(i+reqh+1, reqh+(m-1))+num))%mod;
  97.         ans=(ans + exp)%mod;
  98.     }
  99.     return ans;
  100. }
  101. int32_t main()
  102. {
  103.     pre();
  104.     int n, m, k;
  105.     cin>>n>>m>>k;
  106.     cout<<solve2(n, m, k);
  107. }
Success #stdin #stdout 2.4s 66052KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/V2vGBp
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!