Sep 12, 2019 由 小羊
考虑形如
形式的多项式,它的一阶导函数为
则可以发现它们之间有
则有
由于根重数不同,每个根的因子会在不同时刻从上式消失。每次将 当作新的 进行迭代即可。
另外,STL好慢啊233。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 998244353;
typedef vector<int> Poly;
inline lld fpow(lld a, int k)
{
lld b = 1;
for (; k; k>>=1, a=a*a%MOD)
if (k&1) b=b*a%MOD;
return b;
}
void norm(Poly &a)
{
lld qwq = fpow(a.back(), MOD-2);
for (auto &x : a) x = x * qwq % MOD;
}
Poly diff(const Poly &a)
{
Poly _a = Poly(a.size() - 1);
for (int i = 0; i < _a.size(); i++)
_a[i] = a[i+1] * (i+1LL) % MOD;
return _a;
}
void divide(const Poly &a, const Poly &p, Poly &q, Poly &r)
{
assert(p.size() >= 1 && p.back() != 0);
q.clear(), r = a; int P = p.size();
lld pq = fpow(p.back(), MOD-2);
for (int i = a.size()-1; i >= P-1; i--)
{
q.push_back(r[i] * pq % MOD);
for (int j = 0; j < P; j++)
r[i-P+1+j] = (r[i-P+1+j] + MOD - 1LL * r[i] * pq % MOD * p[j] % MOD) % MOD;
}
reverse(q.begin(), q.end());
while (q.back() == 0) q.pop_back();
while (r.back() == 0) r.pop_back();
}
Poly gcd(Poly a, Poly b)
{
Poly c, d;
while (b.size()) divide(a, b, c, d), a = b, b = d;
norm(a);
return a;
}
void solve()
{
int n; scanf("%d", &n); vector<pair<int,int>> ans;
Poly orig(n+1, 0), dif, cbs, tmp, nil, nul;
for (int i = 0; i <= n; i++) scanf("%d", &orig[i]);
norm(orig); dif = diff(orig), tmp = gcd(orig, dif);
divide(orig, tmp, cbs, nil); orig = tmp, norm(orig);
for (int l = 1; dif.size(); l++)
{
dif = diff(orig), tmp = gcd(orig, dif);
divide(orig, tmp, nul, nil);
if (nul != cbs)
{
// an root appears!
Poly a, b;
divide(cbs, nul, b, a);
assert(b.size() == 2);
ans.emplace_back((MOD-b[0])%MOD, l);
cbs = nul;
}
orig = tmp, norm(orig);
}
printf("%d\n", int(ans.size()));
for (auto p : ans) printf("%d %d\n", p.first, p.second);
}
int main()
{
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}