LOJ 劳孙肉饼

题目链接

XRRRRQAQ 去学文化的的样子太萌啦！！！

XRRRRQAQ 在课上太无聊，以至于吃起了劳孙（你不用知道这是什么）

显然劳孙是一个 N * M 的肉饼（即N行 M 列）

XRRRRQAQ 每次可以将一个矩形劳孙啃下来一行或一列

XRRRRQAQ 每吃一次劳孙都可能引起劳师的注意，这很刺激

XRRRRQAQ 为了寻求最多的刺激，打算用最多的次数吃完这个大劳孙

他想问你：他最多刺激几次呢？？答案对 1e9+7 取模

样例输入 1

2 3

样例输出 1

样例解释 1

先啃掉第 2 列，然后就剩下了两个 2 * 1 的小肉饼，每个都可以啃 2 次（先啃掉一行，再啃掉另一行）

故输出 5

样例输入 2

3 10

样例输出 2

样例输入 3

100 200

样例输出 3

$N , M <= 10^{18}$ 时间限制 50 ms

这题n，m这么大，肯定是个贪心，先用dp打表，发现让 n <= m(好像无所谓，不过这样打表明显一点)

从 1 开始枚举m ，

发现

第一项是 n
之后每一项类似等差数列
当 n 为奇数时，公差为 $(n + 1) / 2$
当 n 为偶数是，公差交替为$n / 2$ 与$ n / 2 + 1$ ，（就是交替进行）

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod = 1e9+7;

const int N = 310;

int n , m;

int dp[N][N];

int calc(int n , int m) // 打表

{

	if(n <= 0 || m <= 0) return dp[n][m] = 0;

	if(n == 1) return dp[n][m] = m;

	if(m == 1) return dp[n][m] = n;

	if(~dp[n][m]) return dp[n][m];

	register int ans = 0 , i;

	for(i = 1 ; i <= n ; ++i) ans = max(ans , calc(i - 1 , m) + calc(n - i , m) + 1);

	for(i = 1 ; i <= m ; ++i) ans = max(ans , calc(n , i - 1) + calc(n , m - i) + 1);

	return dp[n][m] = ans;

}

long long mul(long long a , long long k)

{

	long long ans = 0; a %= mod;

	for( ; k ; k >>= 1 , a = (a + a) % mod)

		if(k & 1) ans = (ans + a) % mod;

	return ans;

}

int main()

{

	long long n , m; cin >> n >> m;

	if(n > m) swap(n , m);

	if(n & 1)

	{

		long long d = (n + 1) / 2;

		cout << (n + mul(d , m - 1)) % mod << endl;

	}

	else

	{

		long long d1 = n / 2 , d2 = d1 + 1; m--;

		cout << ((n + mul((m + 1) / 2 , d1)) % mod + mul(m - (m + 1) / 2 , d2)) % mod << endl;

	}

	return 0;

}

巴特西