Description
Fan Li (范蠡) was an ancient Chinese advisor in the state of Yue in the Spring and Autumn period. He is a successful militarist and a successful business man. He is one of the main characters of a famous Chinese proverb “卧薪尝胆”. One day, when he was training the army, he came up with an idea, if he let all the soldiers stand in a line (every soldier has a fighting capacity), what is the maximum disjoint intervals he can choose so that the greatest common divisor of all the intervals are equal, and how many ways can he choose the maximum disjoint intervals satisfy the condition. The different ways may be very large, output the answer mod 998244353.
Input
There are multiple test cases.
Each test cases begins with an integer n, then followed n positive integers.
1 <= n <= 100000
All the integers are less than 2333333.
Output
For each test case, output the number of maximum intervals and the ways of reach the maximum number.
Sample Input
3 1 2 3 5 1 2 2 2 2 3 1 2 1
Sample Output
2 1 4 1
2 3
一道比较恶心的gcd题目，询问最多分几段不想交的区间满足gcd值相等，并且询问有多少种方案。
先计算出以[1,n]为右端点的全部的gcd的值及对应范围，记为(l,ll,r,x)，即左端点在[l,ll],
右端点在r的全部区间的gcd值都为x，然后按照x的大小排序，再按r的大小排序。
然后对于相同的x，我们可以用dp[i]来表示第i个点的最大分段，
我们用二分找到第一个r小于ll的点j，显然dp[i]=dp[j]+1，这样就可以统计出最大的分段。
计算方案数的话，对于全部的满足dp[i]=dp[k]+1且k<=j的点来说，分为两种，
如果这个点的r小于l，那么显然贡献为s[k]*(ll-l+1)种
如果这个点大于等于l，那么答案是s[k]*(ll-k)种，于是统计一下前缀和即可。
#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 998244353;
const int N = 1e5 + 10;
int n, x[N], sz;
int gcd(int x, int y)
{
return x%y ? gcd(y, x%y) : y;
}
struct point
{
int l, ll, r, x;
point(int l = 0, int ll = 0, int r = 0, int x = 0) :l(l), ll(ll), r(r), x(x) {};
bool operator<(const point&a) const
{
return r < a.r;
}
}p[N * 30], q[N];
int L[N], R[N], dp[N];
LL s1[N], s2[N];
bool cmp(const point &a, const point &b)
{
return a.x == b.x ? a.r < b.r : a.x < b.x;
}
void getpoint()
{
stack<pii> a, b;
sz = 1;
rep(i, 1, n)
{
a.push(mp(x[i], 1));
while (!a.empty()) b.push(mp(gcd(a.top().ff, x[i]), a.top().ss)), a.pop();
while (!b.empty())
{
pii q = b.top(); b.pop();
if (!a.empty() && a.top().ff == q.ff) q.ss += a.top().ss, a.pop();
a.push(q);
}
while (!a.empty()) b.push(a.top()), a.pop();
int bef = 0;
while (!b.empty())
{
p[sz++] = point(bef + 1, bef + b.top().ss, i, b.top().ff);
bef += b.top().ss;
a.push(b.top()), b.pop();
}
}
}
int main()
{
while (scanf("%d", &n) != EOF)
{
rep(i, 1, n) scanf("%d", &x[i]);
getpoint(); sort(p + 1, p + sz, cmp);
LL ans = 0, cnt = 0;
for (int i = 1, j = 1; i < sz; i = j)
{
int tot = L[1] = R[1] = 0;
s1[0] = s2[0] = dp[0] = 0; dp[1] = 1;
for (; j < sz&&p[i].x == p[j].x; j++) q[++tot] = p[j];
rep(k, 2, tot)
{
int g = lower_bound(q + 1, q + k, point(0, 0, q[k].ll)) - q - 1;
dp[k] = dp[g] + 1;
if (dp[k] == dp[k - 1]) L[k] = L[k - 1], R[k] = g;
else
{
L[k] = R[k] = g;
while (dp[L[k] - 1] + 1 == dp[k]) L[k]--;
}
}
rep(k, 1, tot)
{
if (dp[k] == 1) s1[k] = q[k].ll - q[k].l + 1;
else
{
int g = lower_bound(q + L[k], q + R[k] + 1, point(0, 0, q[k].l)) - q - 1;
s1[k] = 0;
if (g >= L[k]) s1[k] += (s1[g] - s1[L[k] - 1]) * (q[k].ll - q[k].l + 1);
if (g <= R[k]) s1[k] += (s1[R[k]] - s1[g]) * q[k].ll - (s2[R[k]] - s2[g]);
s1[k] %= mod;
}
if (ans < dp[k]) ans = dp[k], cnt = s1[k];
else if (ans == dp[k]) cnt += s1[k];
s2[k] = (s2[k - 1] + s1[k] * q[k].r) % mod;
s1[k] = (s1[k] + s1[k - 1]) % mod;
cnt = (cnt % mod + mod) % mod;
}
}
printf("%lld %lld\n", ans, cnt);
}
return 0;
}