欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

表格(拉格朗日插值法)

程序员文章站 2022-03-13 12:57:47
...

众所周知,Logx精通Excel。
他觉得表格只有单调的白色非常无聊,他决定将一些单元格涂黑。

在一个n行m列的表格里,刚开始所有单元格都是白的。
Logx打算在这个表格选出三个不同的单元格A(x1,y1),B(x2,y2),C(x3,y3),并将选中的三个单元格涂黑。
为了使表格看起来美观,Logx会使每一行和每一列均至多有一个格子被涂黑。
他称一种选择方案是好的,当且仅当L≤|x1-x2|+|y1-y2|+|x2-x3|+|y2-y3|+|x1-x3|+|y1-y3|≤R,即这三个黑格子之间两两的曼哈顿距离之和在区间[L,R]内。其中L,R是他给定的两个常数。
两种方案不同,当且仅当存在一个格子,在一种方案中被涂黑了,在另一种方案中没有被涂黑。
Logx想要知道,有多少种选择方案是好的。
 

输入

输入仅一行,包含四个正整数 n,m,L,R,含义见题目描述。

输出

输出一行一个整数表示方案数。
由于答案可能很大,你只要输出方案数对10^9+7取模的结果。

 

样例输入 Copy

【样例1】
3 3 1 20000
【样例2】
3 3 4 7
【样例3】
4 6 9 12
【样例4】
7 5 13 18
【样例5】
4000 4000 4000 14000

样例输出 Copy

【样例1】
6
【样例2】
0
【样例3】
264
【样例4】
1212
【样例5】
859690013

提示

对于所有数据,3≤n,m≤10^16,1≤L≤R≤10^18。

 

结论:

1. 设三个不在同行同列的黑格子所围成的长方形为x * y,那么三个黑格子两两之间距离和为2 * (x + y - 2);

2. 设三个不在同行同列的黑格子所围成的长方形为x * y,有6 * (x - 2) * (y - 2)种方法放置三个黑格子;

3. 一个大小为x * y的长方形在n * m的格子中有(n - x + 1) * (m - y + 1);

 

首先将(L, R)区间拆成(1,R) - (1, L - 1)

所以

表格(拉格朗日插值法)

表格(拉格朗日插值法)

表格(拉格朗日插值法)

 

 

表格(拉格朗日插值法)

H1(x)用拉格朗日插值法算出来

H2(x)可以直接用公式或者同第一步用拉格朗日插值

最暴力的代码O(n*m)

/**/
#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const long long mod = 1e9 + 7;

LL n, m, l, r;
LL pw6, pw2;

LL poww(LL x, LL num){
	LL res = 1;
	while(num){
		if(num & 1) res = res * x % mod;
		x = x * x % mod;
		num >>= 1;
	}
	return res;
}

LL cal(LL x, LL y){
	return (x - 2) * (y - 2) % mod * 6 % mod;
}

LL cal1(LL x){
	return x * (x + 1) % mod * (2 * x + 1) % mod * pw6 % mod;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	pw6 = poww(6, mod - 2);
	pw2 = poww(2, mod - 2);
	scanf("%lld %lld %lld %lld", &n, &m, &l, &r);
	LL ans = 0;
	for (LL i = 3; i <= min(r / 2 - 1, n); i++){
		LL L = max(3LL, (l + 1) / 2 + 2 - i), R = min(2 - i + r / 2, m);
		for (LL j = L; j <= R; j++){
			ans += cal(i % mod, j % mod) * ((n - i + 1) % mod) % mod * ((m - j + 1) % mod) % mod;
			ans %= mod;
		}
	}
	printf("%lld\n", ans);

	return 0;
}
/**/

暴力代码(n)

/**/
#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const long long mod = 1e9 + 7;

LL n, m, l, r;
LL pw6, pw2;

LL poww(LL x, LL num){
	LL res = 1;
	while(num){
		if(num & 1) res = res * x % mod;
		x = x * x % mod;
		num >>= 1;
	}
	return res;
}

LL cal(LL x, LL y){
	return (x - 2) * (y - 2) % mod * 6 % mod;
}

LL cal1(LL x){
	return x * (x + 1) % mod * (2 * x + 1) % mod * pw6 % mod;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	pw6 = poww(6, mod - 2);
	pw2 = poww(2, mod - 2);
	scanf("%lld %lld %lld %lld", &n, &m, &l, &r);
	LL ans = 0;
	for (LL i = 3; i <= min(r / 2 - 1, n); i++){
		LL L = max(3LL, (l + 1) / 2 + 2 - i), R = min(2 - i + r / 2, m);
		LL t1 = (cal1((L - 1) % mod) - cal1(R % mod)) % mod;
		LL t2 = (m + 3) % mod * ((R - L + 1) % mod) % mod * ((R + L) % mod) % mod * pw2 % mod;
		LL t3 = 2 * (m + 1) % mod * ((R - L + 1) % mod) % mod;
		LL t = ((t1 + t2 - t3) % mod + mod) % mod;
		ans = (ans + t * 6 % mod * ((i - 2) % mod) % mod * ((n - i + 1) % mod) % mod) % mod;
	}
	printf("%lld\n", ans);

	return 0;
}
/**/

AC代码:

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int D = 1e3 + 10;

const long long mod = 1e9 + 7;

LL n, m, l, r, R, pw2, pw6;
LL a[D], f[D], g[D], p[D], p1[D], p2[D], b[D], h[D][2], C[D];

LL poww(LL x, LL num){
	LL res = 1;
	while(num){
		if(num & 1) res = res * x % mod;
		x = x * x % mod;
		num >>= 1;
	}
	return res;
}

void init(int M){
	f[0] = f[1] = g[0] = g[1] = 1;
	for (int i = 2; i <= M + 4; i++) f[i] = f[i - 1] * i % mod;
	g[M + 4] = poww(f[M + 4], mod - 2);
	for (int i = M + 3; i >= 1; i--) g[i] = g[i + 1] * (i + 1) % mod;
}

LL sum(LL x, LL y){
	return ((x - 2) % mod) * ((y - x + 1) % mod) % mod;
}

LL calcn(int d, LL *a, LL n){// a[0].. a[d]  a[n]
	if(n <= d) return a[n];
	p1[0] = p2[0] = 1;
	for (int i = 0; i <= d; i++){
		LL t = (n - i + mod) % mod;
		p1[i + 1] = p1[i] * t % mod;
	}
	for (int i = 0; i <= d; i++){
		LL t = (n - d + i + mod) % mod;
		p2[i + 1] = p2[i] * t % mod;
	}
	LL ans = 0;
	for (int i = 0; i <= d; i++){
		LL t = g[i] * g[d - i] % mod * p1[i] % mod * p2[d - i] % mod * a[i] % mod;
		if((d - i) & 1) ans = (ans - t + mod) % mod;
		else ans = (ans + t) % mod;
	}
	return ans;
}

LL polysum(LL m, LL *a, LL n){// a[0].. a[m] \sum_{i=0}^{n} a[i]
	if(n <= m){
		LL sum = 0;
		for (int i = 0; i <= n; i++) sum = (sum + a[i]) % mod;
		return sum;
	}
	LL b[D];
	for (int i = 0; i <= m; i++) b[i] = a[i];
	b[m + 1] = calcn(m, b, m + 1);
	for (int i = 1; i <= m + 1; i++) b[i] = (b[i - 1] + b[i]) % mod;
	return calcn(m + 1, b, n);// m次多项式的和是m+1 次多项式
}

LL cal3(LL x){
	return x * (x + 1) % mod * (2 * x + 1) % mod * pw6 % mod;
}

LL solve(LL L, LL R){
	if(L > R) return 0LL;
	LL t1 = (cal3((L - 1) % mod) - cal3(R % mod)) % mod;
	LL t2 = (m + 3) % mod * ((R - L + 1) % mod) % mod * ((R + L) % mod) % mod * pw2 % mod;
	LL t3 = 2 * (m + 1) % mod * ((R - L + 1) % mod) % mod;
	LL t = ((t1 + t2 - t3) % mod + mod) % mod;
	return t;
}

LL cal1(LL l, LL r){
	if(l > r) return 0LL;
	LL a[15];
	for (int i = 0; i <= 5; i++) a[i] = sum(l + i, n) * solve(3, R / 2 - l - i + 2) % mod;
	return polysum(5, a, r - l);
}

LL cal2(LL l, LL r){
	if(l > r) return 0LL;
	LL a[15];
	a[0] = 0;
	for (int i = 0; i <= 2; i++) a[i] = sum(l + i, n) * solve(3, m) % mod;
	return polysum(2, a, r - l);
}

LL cal(LL x){
	if(!x) return 0LL;
	LL L1 = x / 2 - m + 2, R1 = min(n, x / 2 - 1);
	LL L2 = 3, R2 = x / 2 - m + 1;
	if(R2 < L2) return cal1(max(3LL, L1), R1);
	else if(R2 >= n) return cal2(L2, min(R2, n));
	else return cal1(L1, R1) + cal2(L2, R2);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	pw2 = poww(2, mod - 2), pw6 = poww(6, mod - 2);
	init(1000);
	scanf("%lld %lld %lld %lld", &n, &m, &l, &r);
	R = r;
	LL ans = cal(r);
	R = l - 1;
	ans -= cal(l - 1);
	printf("%lld\n", (ans + mod) % mod * 6 % mod);

	return 0;
}
/**/

 

相关标签: 拉格朗日插值