小A的多项式

C++14(g++5.4) 解法, 执行用时: 1601ms, 内存消耗: 90948K, 提交时间: 2019-03-14 19:55:10

#include<vector>
#include<cstdio>
#define pp printf
#define ll long long
#define fo(i, x, y) for(int i = x, E = y; i <= E; i ++)
#define ff(i, x, y) for(int i = x, E = y; i <  E; i ++)
#define fd(i, x, y) for(int i = x, E = y; i >= E; i --)
using namespace std;
 
const int mo = 998244353;
 
ll ksm(ll x, ll y) {
    ll s = 1;
    for(; y; y /= 2, x = x * x % mo)
        if(y & 1) s = s * x % mo;
    return s;
}
 
typedef vector<ll> V;
 
const int N = 6005;
 
ll d[N], A[N], B[N];
 
V operator *(V a, V b) {
    int sc = a.size() + b.size() - 1;
    ff(i, 0, a.size()) A[i] = a[i];
    ff(i, 0, b.size()) B[i] = b[i];
    ff(i, 0, sc) d[i] = 0;
    ff(i, 0, a.size()) ff(j, 0, b.size()) d[i + j] += A[i] * B[j] % mo;
    ff(i, 0, sc) d[i] %= mo;
    V c; c.resize(sc);
    ff(i, 0, sc) c[i] = d[i];
    return c;
}
 
V operator %(V a, V b) {
    int sa = a.size(), sb = b.size();
    ff(i, 0, sa) A[i] = a[i];
    ff(i, 0, sb) B[i] = b[i];
    ll nb = ksm(B[sb - 1], mo - 2);
    fd(i, sa - 1, sb - 1) {
        ll c = A[i] * nb % mo;
        ff(j, 0, sb) A[j + i - (sb - 1)] -= B[j] * c % mo, A[j + i - (sb - 1)] %= mo;
    }
    ff(i, 0, sa) a[i] = A[i];
    while(sa > 1 && !a[sa - 1]) sa --; a.resize(sa);
    return a;
}
 
int n, k;
V f, s;
 
void ksm(int y) {
    V x; x.clear(); x.resize(2);
    x[0] = 0; x[1] = 1;
    s.clear(); s.push_back(1);
    for(; y; y /= 2, x = x * x % f) {
        if(y & 1) s = s * x % f;
    }
}
 
void Ksm(int y) {
    V x = s; s.clear(); s.push_back(1);
    for(; y; y /= 2, x = x * x % f)
        if(y & 1) s = s * x % f;
}
 
V gcd(V a, V b) {
    if(b.size() == 1 && !b[0]) return a;
    return gcd(b, a % b);
}
 
int main() {
	//freopen("in.txt","r",stdin);
    scanf("%d %d", &n, &k); n ++;
    f.resize(n); ff(i, 0, n) scanf("%lld", &f[i]);
    ksm((mo - 1) / 2);
    s[0] --;
    Ksm(k);
    s = gcd(f, s);
    ff(i, 0, s.size()) s[i] = (s[i] + mo) % mo;
    ll t = ksm(s[s.size() - 1], mo - 2);
    pp("%d\n", s.size() - 1);
    ff(i, 0, s.size()) pp("%lld ", s[i] * t % mo);
}

C++11(clang++ 3.9) 解法, 执行用时: 1813ms, 内存消耗: 15592K, 提交时间: 2019-11-22 22:57:11

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
const int P=998244353;
inline int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%P)if(b&1)r=1ll*r*a%P;return r;} 
inline vi mul(const vi&a,const vi&b)
{
	int n=a.size(),m=b.size();vi r;r.resize(n+m-1);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)r[i+j]=(r[i+j]+1ll*a[i]*b[j])%P;
	while(r.size()&&!r.back())r.pop_back();return r;
}
inline vi mod(const vi&a,const vi&b)
{
	int n=a.size(),m=b.size();vi r=a;
	for(int i=n-1;i>=m-1;i--)if(r[i])
	{
		int t=1ll*(P-r[i])*pw(b[m-1],P-2)%P;
		for(int j=0;j<m;j++)r[i-j]=(r[i-j]+1ll*b[m-1-j]*t)%P;
	}
	while(r.size()&&!r.back())r.pop_back();return r;
}
inline vi pw(vi a,int b,const vi&p){vi r;r.pb(1);for(;b;b>>=1,a=mod(mul(a,a),p))if(b&1)r=mod(mul(r,a),p);return r;}
vi gcd(const vi&a,const vi&b){return b.size()?gcd(b,mod(a,b)):a;}
int main()
{
	int n,k;scanf("%d%d",&n,&k);vi f,g;
	for(int i=0,x;i<=n;i++)scanf("%d",&x),f.pb(x);
	g.pb(0);g.pb(1);g=pw(g,(P-1)/2,f);
	if(!g.size())g.pb(P-1);else g[0]=(g[0]+P-1)%P;
	g=pw(g,k,f);g=gcd(g,f);int t=pw(g[g.size()-1],P-2);
	printf("%d\n",(int)g.size()-1);
	for(int i=0;i<g.size();i++)printf("%d ",1ll*g[i]*t%P);
	return 0;
}

详情