[LOJ6464] 劳孙肉饼

Description

给定一块 (n imes m (n,m le 10^{18})) 的网格形巧克力，初态下连通，每次可以吃掉某一个连通块上的一行或一列，这可能导致这个连通块段成两个连通块。求吃完的最大步数。

Solution

设 (f(x,y)) 表示对于 (x imes y) 的巧克力的答案，由于对称性，不妨设 (x le y)，则很显然有

[f(x,y)=max(f(x,j)+f(x,y-j-1))+1 ]

对 (f(1,y),f(2,y),...,f(x,y)) 找规律容易得到

[f(x,y)=frac {xy+x+y-1}{2} ]

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define lint __int128_t
const int N = 100005;
const int mod = 1e9+7;
const int dbg = 1;

signed main()
{
    int x,y;
    cin>>x>>y;
    lint ans=((lint)x*y+x+y-1)/2;
    cout<<(int)(ans%mod)<<endl;
    if(dbg) system("pause");
}