描述
题解
在 n∗m 的区域中,有 n∗m 种知了,给出每种知了第一次出现的年数 s 和周期性
这里要求矩形区域中所有知了第一次同时出现的年数,我们可以先从两只知了考虑,设甲第一次出现、甲出现周期、甲出现的次数、甲出现的年数、乙第一次出现、乙出现周期、乙出现的次数、乙出现的年数为 s1、z1、c1、d1、s2、z2、c2、d2 ,那么我们很容易得到:
因为想要两只同时出现,所以使 d1=d2 联立得:
所以利用扩展欧几里得我们可以得到 c1 的最小正整数解,代入可得 d 值。这样得到了第一次两只知了同时出现的年数,那么以后两只知了同时出现的年数也是周期性的,周期为
考虑完两只知了的合并后,就可以考虑更多的合并了,其实我们完全可以将已经合并的两只看成一只,然后再与其他的进行合并,如此这般我们便能很容易获得到任意只知了同时出现的时间。
由于题目 0<n,m≤200 ,但是 0<1≤50000 ,所以我们需要先预处理出来一些信息这样才能更好的优化访问。我们不妨用 DP 设 dp[i][j][k] 表示第 i 行从
现在来分析复杂度,首先预处理的复杂度是
除此之外,还有一个比较明显的问题便是 longlong 会爆,在计算的时候产生的中间变量会爆掉 longlong ,所以那部分我们需要用更大的数据类型来保存,恰好有一个叫做 __int128 的玩意儿,可以好好用用。
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int MAXN = 202;
const int MAXM = MAXN * MAXN / 2 + MAXN;
struct node
{
ll a, b;
} dp[MAXN][MAXM];
int n, m, q;
inline int _hash(int x, int y)
{
return (2 * m - x + 1) * x / 2 + y - x + 1;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll ans = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
return ans;
}
node merge(node x, node y)
{
if (x.a == -1 || y.a == -1)
{
return {-1, -1};
}
ll _x, _y;
ll g = exgcd(x.b, y.b, _x, _y);
if ((y.a - x.a) % g)
{
return {-1, -1};
}
ll t = (y.a - x.a) / g;
lll p = x.a + (lll)x.b * _x * t;
lll q = x.b / g * y.b;
p = (p % q + q) % q;
return {(ll)p, (ll)q};
}
void init()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (int k = j + 1; k < m; k++)
{
dp[i][_hash(j, k)] = merge(dp[i][_hash(k, k)], dp[i][_hash(j, k - 1)]);
}
}
}
}
int main(int argc, const char * argv[])
{
int T;
cin >> T;
for (int ce = 1; ce <= T; ce++)
{
printf("Case #%d:\n", ce);
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
scanf("%lld", &dp[i][_hash(j, j)].a);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
scanf("%lld", &dp[i][_hash(j, j)].b);
}
}
init();
scanf("%d", &q);
int x1, y1, x2, y2;
while (q--)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x1--; y1--; x2--; y2--;
node ans = dp[x1][_hash(y1, y2)];
for (int i = x1 + 1; i <= x2; i++)
{
if (ans.a == -1)
{
break;
}
ans = merge(ans, dp[i][_hash(y1, y2)]);
}
printf("%lld\n", ans.a);
}
}
return 0;
}