Rectangle

frog has a piece of paper divided into nn rows and mm columns. Today, she would like to draw a rectangle whose perimeter is not greater than kk.

There are 88 (out of 99) ways when n=m=2,k=6n=m=2,k=6

Find the number of ways of drawing.

Input

The input consists of multiple tests. For each test:

The first line contains 33 integer n,m,kn,m,k (1≤n,m≤5⋅104,0≤k≤1091≤n,m≤5⋅104,0≤k≤109).

Output

For each test, write 11 integer which denotes the number of ways of drawing.

Sample Input

    2 2 6

    1 1 0

    50000 50000 1000000000

Sample Output

    8

    0

    1562562500625000000
解析：枚举矩形的长h，然后它在h的方向上就有n-h+1种放法，同时宽的最大值w即为k/2 - h，对于每个0~w的宽度wi，它在w方向上的放法有m-wi+1种，求和即为所求方案数

我推出了数学公式
n*m中a*b的种数：（n-a+1）*(m-b+1)+(m-a+1)*(n-b+1)
这样仍会超时：a不变，b变化，推出一个公式。
1^2+2^2+3^2+……+n^2=n*(n+1)*(2*t+1)/6;

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#define  ll long long

using namespace std;

int main()

{

    ll n,m,k;

    while(~scanf("%lld %lld %lld",&n,&m,&k))

    {

        ll s=;

        ll temp;

        if(k<&&k>=) s=n*m;

        else if(k<) s=;

        else

        {

            if(n>m)

            {

                temp=n;

                n=m;

                m=temp;

            }

            for(ll a=;a<=n;a++)

            {

                ll b=min(k/-a,m);

                if(b>=a)

                {

                    s+=(n-a+)*((m-a+)+(m-b+))*(b-a+)/;

                }

                b=min(k/-a,n);

                if(b>=a)

                {

                    s+=(m-a+)*((n-a+)+(n-b+))*(b-a+)/;

                }

            }

            ll t=min(k/,n);

            t=min(t,m);

            ll ss=;

            ss+=(t*(t+)*(*t+))/-(t+)*t*(n+m+)/+(n*m++n+m)*t;//中间有重复的情况，a=b的算了两次

            s=s-ss;

        }

        printf("%lld\n",s);

    }

    return ;

}

也有更简单的思路：

#include <bits/stdc++.h>

using namespace std;  

int main(){

    #ifdef sxk

        freopen("in.txt", "r", stdin);

    #endif // sxk  

    long long n, m, k;

    while(cin>>n>>m>>k){

        k /= ;

        long long ans = ;

        for(int h=; h<=n; h++){

            int w = k - h;

            if(w <= ) break;

            if(w > m) w = m;

            ans += (n - h + ) * (m + m-w+)*w/;    //对于每个h，在h方向上n-h+1种，在w方向上枚举wi求和为(m + m-w+1) * w / 2种

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

四川第七届 E Rectangle

Rectangle

Input

Output

Sample Input

Sample Output

最新文章

热门文章