标签：多项式

CFGYM103415A CCPC2021广州A Math Ball

2021年11月26日 by officeyutong·一条评论

题意: 有$n$种球，每种有无限个，同时第$i$种球有一个代价$c_i$，你要拿不超过$w$个球。如果最后第$i$种球你拿了$k_i$个，那么你会获得$\prod_{1\leq 阅读全文..

跑的比较快的多项式板子

2021年11月13日 by officeyutong·0评论

#include <cstring>
#include <iostream>
#include <random>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2e6;

const int_t mod = 998244353;
const int_t g = 3;
int_t power(int_t b, int_t i) {
    int_t r = 1;
    if (i < 0)
        i = (i % (mod - 1) + mod - 1) % (mod - 1);
    while (i) {
        if (i & 1)
            r = r * b % mod;
        b = b * b % mod;
        i >>= 1;
    }
    return r;
}

void makeflip(int_t* arr, int_t size2) {
    int_t len = (1 << size2);
    arr[0] = 0;
    for (int_t i = 1; i < len; i++) {
        arr[i] = (arr[i >> 1] >> 1) | ((i & 1) << (size2 - 1));
    }
}

int_t upper2n(int_t x) {
    int_t r = 0;
    while ((1 << r) < x)
        r++;
    return r;
}
template <int_t arg = 1>
void transform(int_t* A, int_t size2, int_t* flip) {
    int_t len = (1 << size2);
    for (int_t i = 0; i < len; i++) {
        int_t r = flip[i];
        if (r > i)
            std::swap(A[i], A[r]);
    }
    for (int_t i = 2; i <= len; i *= 2) {
        int_t mr = power(g, arg * (mod - 1) / i);
        for (int_t j = 0; j < len; j += i) {
            int_t curr = 1;
            for (int_t k = 0; k < i / 2; k++) {
                int_t u = A[j + k], v = curr * A[j + k + i / 2] % mod;
                A[j + k] = (u + v) % mod;
                A[j + k + i / 2] = (u - v + mod) % mod;
                curr = curr * mr % mod;
            }
        }
    }
}
void poly_inv(const int_t* A, int_t n, int_t* result) {
    /*
    这里的n是模x^n
    计算B(x)*A(x) = 1 mod x^n, 其中A(x)已知
    假设已知A(x)*B(x) = 1 mod x^{ceil(n/2)}
    假设C(x)*A(x) = 1 mod x^n
    (A(x)B(x)-1)^2 = A^2(x)B^2(x)-2A(x)B(x)+1= 0
    A(x)B^2(x)-2B(x)+C(x) = 0
    C(x) = 2B(x)-A(x)B^2(x)
    */
    // #ifdef DEBUG
    //     cout << "at " << n << endl;
    // #endif
    if (n == 1) {
        result[0] = power(A[0], -1);
        return;
    }
    int_t next = n / 2 + n % 2;
    poly_inv(A, next, result);
    //次数不要选错了，应该用n次的A和B去卷
    int_t size2 = upper2n(n + 2 * next + 1);
    static int_t X[LARGE];
    static int_t Y[LARGE];
    int_t len = (1 << size2);
    // 写错设置范围了！
    memset(X + n, 0, sizeof(X[0]) * (len - n));
    memset(Y + next, 0, sizeof(Y[0]) * (len - next));
    memcpy(X, A, sizeof(A[0]) * n);
    memcpy(Y, result, sizeof(result[0]) * next);
    static int_t fliparr[LARGE];
    makeflip(fliparr, size2);
    transform<1>(X, size2, fliparr);
    transform<1>(Y, size2, fliparr);

    for (int_t i = 0; i < len; i++) {
        X[i] = (2 * Y[i] - X[i] * Y[i] % mod * Y[i] % mod + mod) % mod;
    }
    transform<-1>(X, size2, fliparr);
    const int_t inv = power(len, -1);
    for (int_t i = 0; i < n; i++)
        result[i] = X[i] * inv % mod;
#ifdef DEBUG
    cout << "poly inv at " << n << endl;
    cout << "result = ";
    for (int_t i = 0; i < next; i++)
        cout << result[i] << " ";
    cout << endl;

#endif
}
int_t poly_divat(const int_t* F, const int_t* G, int_t n, int_t k) {
    /*
        n次多项式F和G
        计算F(x)/G(x)的k次项前系数
        考虑F(x)*G(-x)/G(x)*G(-x)，分母只有偶数次项，写为C(x^2)；分子写成xA(x^2)+B(x^2)，如果k是奇数，那么递归(A,C,n,k/2)，如果k是偶数，那么递归(B,C,n,k/2)
        到k<=n时直接计算
    */
    int_t size2 = upper2n(2 * n + 1);
    int_t len = 1 << size2;
    static int_t fliparr[LARGE];
    makeflip(fliparr, size2);
    static int_t T1[LARGE], T2[LARGE], T3[LARGE];
    for (int_t i = 0; i < len; i++) {
        if (i <= n)
            T1[i] = F[i], T2[i] = G[i];
        else
            T1[i] = T2[i] = T3[i] = 0;
    }
    const int_t inv = power(len, -1);
    while (k >= n) {
#ifdef DEBUG
        cout << "curr at k = " << k << endl;
#endif
        for (int_t i = 0; i < len; i++) {
            if (i <= n) {
                T3[i] = T2[i] * (i % 2 ? (mod - 1) : 1);
            } else
                T3[i] = 0;
        }
        transform(T1, size2, fliparr);
        transform(T2, size2, fliparr);
        transform(T3, size2, fliparr);
        for (int_t i = 0; i < len; i++) {
            T1[i] = T1[i] * T3[i] % mod;
            T2[i] = T2[i] * T3[i] % mod;
        }
        transform<-1>(T1, size2, fliparr);
        transform<-1>(T2, size2, fliparr);
#ifdef DEBUG
        cout << "prod T1 = ";
        for (int_t i = 0; i < len; i++)
            cout << T1[i] * inv % mod << " ";
        cout << endl;
        cout << "prod T2 = ";
        for (int_t i = 0; i < len; i++)
            cout << T2[i] * inv % mod << " ";
        cout << endl;

#endif
        for (int_t i = 0; i < len; i++) {
            if (i * 2 < len) {
                T2[i] = T2[i * 2] * inv % mod;
            } else
                T2[i] = 0;
        }
        int_t b = k % 2;
        for (int_t i = 0; i < len; i++) {
            if (i % 2 == b) {
                T1[i / 2] = T1[i] * inv % mod;
#ifdef DEBUG
                cout << "at " << i << " assgin " << T1[i] * inv << " to "
                     << i / 2 << endl;
#endif
            }
#ifdef DEBUG
            cout << "assign 0 to " << i << endl;
#endif
            if (i > 0)
                T1[i] = 0;
        }
#ifdef DEBUG
        cout << "finished T1 = ";
        for (int_t i = 0; i < len; i++)
            cout << T1[i] % mod << " ";
        cout << endl;
        cout << "finished T2 = ";
        for (int_t i = 0; i < len; i++)
            cout << T2[i] % mod << " ";
        cout << endl;

#endif
        k >>= 1;
    }

    poly_inv(T2, k + 1, T3);
    // #ifdef DEBUG

    //     cout << "finished k = " << k << endl;
    //     cout << "T1 = ";
    //     for (int_t i = 0; i < len; i++)
    //         cout << T1[i] % mod << " ";
    //     cout << endl;
    //     cout << "T2 = ";
    //     for (int_t i = 0; i < len; i++)
    //         cout << T2[i] % mod << " ";
    //     cout << endl;
    //     cout << "T2 inv = ";
    //     for (int_t i = 0; i < len; i++)
    //         cout << T3[i] % mod << " ";
    //     cout << endl;

    // #endif
    int_t result = 0;
    //计算结果的k次项
    for (int_t i = 0; i <= k; i++) {
        result = (result + T1[i] * T3[k - i] % mod) % mod;
    }
    return result;
}
void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
    /*
       计算n次多项式A与m次多项式B的乘积
    */
    int_t size2 = upper2n(n + m + 1);
    int_t len = 1 << size2;
    static int_t T1[LARGE], T2[LARGE];
    for (int_t i = 0; i < len; i++) {
        if (i <= n)
            T1[i] = A[i];
        else
            T1[i] = 0;
        if (i <= m)
            T2[i] = B[i];
        else
            T2[i] = 0;
    }
    static int_t fliparr[LARGE];
    makeflip(fliparr, size2);
    transform(T1, size2, fliparr);
    transform(T2, size2, fliparr);
    for (int_t i = 0; i < len; i++)
        T1[i] = T1[i] * T2[i] % mod;
    transform<-1>(T1, size2, fliparr);
    int_t inv = power(len, -1);
    for (int_t i = 0; i <= n + m; i++)
        C[i] = T1[i] * inv % mod;
}
int_t poly_linear_rec(const int_t* A0, const int_t* F0, int_t n, int_t k) {
    /*
        计算线性递推
        F[1],F[2]...F[k] 递推系数
        A[0],A[1]...A[k-1] 首项

        A[m]=A[m-1]*F[1]+A[m-2]*F[2]+...+A[m-k]*F[k]
    */

    static int_t T1[LARGE], T2[LARGE];
    static int_t Ax[LARGE], Fx[LARGE];
    Fx[0] = 0;
    Ax[k] = 0;
    for (int i = 1; i <= k; i++) {
        Fx[i] = F0[i];
        Ax[i - 1] = A0[i - 1];
    }
    poly_mul(Ax, k, Fx, k, T1);
    T1[0] = Ax[0];
    for (int i = 1; i <= k - 1; i++) {
        T1[i] = (Ax[i] - T1[i] + mod) % mod;
    }
    for (int i = k; i <= 2 * k; i++)
        T1[i] = 0;
    T2[0] = 1;
    for (int i = 1; i <= k; i++)
        T2[i] = (mod - Fx[i]) % mod;

    // #ifdef DEBUG
    //     cout << "T1 = ";
    //     for (int_t i = 0; i <= k; i++) {
    //         cout << T1[i] << " ";
    //     }
    //     cout << endl;
    //     cout << "T2 = ";
    //     for (int_t i = 0; i <= k; i++) {
    //         cout << T2[i] << " ";
    //     }
    //     cout << endl;

    // #endif
    return poly_divat(T1, T2, k, n);
}

void poly_log(const int_t* A, int_t n, int_t* out) {
    /*
        计算log(A(x)), A(x)为n次多项式
        DlogF(x) =DF(x)/F(x)
    */
    static int_t Ad[LARGE];
    static int_t Finv[LARGE];
    static int_t R[LARGE];
    const int_t m = n - 1;
    for (int_t i = 0; i <= m; i++) {
        Ad[i] = A[i + 1] * (i + 1) % mod;
    }
    Ad[n] = 0;
    poly_inv(A, n + 1, Finv);
    poly_mul(Ad, m, Finv, n, R);
    for (int_t i = 1; i <= n; i++) {
        out[i] = R[i - 1] * power(i, -1) % mod;
    }
}
void poly_exp(const int_t* A, int_t n, int_t* out) {
    /*
        计算exp(A(x)), A(x)为n次多项式
        H(x)=G(x)(1-logG(x)+A(x))
        H(x)为当次递推项，G(x)为上一次递推项
    */
    if (n == 1) {
        out[0] = 1;
        return;
    }
    int_t r = n / 2 + n % 2;
    poly_exp(A, r, out);
    static int_t G[LARGE];
    static int_t G2[LARGE];
    static int_t logG[LARGE];
    static int_t R[LARGE];
    for (int_t i = 0; i < r; i++)
        G[i] = out[i];
    for (int_t i = r; i < n; i++)
        G[i] = 0;
    poly_log(G, n - 1, logG);
    // for (int_t i = r; i < n; i++)
    //     logG[i] = 0;
    for (int_t i = 0; i < n; i++) {
        G2[i] = (mod - logG[i] + A[i]) % mod;
    }
    G2[0] = (G2[0] + 1) % mod;
    poly_mul(G, n - 1, G2, n - 1, R);
    for (int_t i = 0; i < n; i++)
        out[i] = R[i];
#ifdef DEBUG
    cout << "at " << n << endl;
    cout << "A = ";
    for (int_t i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << endl;
    cout << "G = ";
    for (int_t i = 0; i < n; i++)
        cout << G[i] << " ";
    cout << endl;
    cout << "logG = ";
    for (int_t i = 0; i < n; i++)
        cout << logG[i] << " ";
    cout << endl;
    cout << "G2 = ";
    for (int_t i = 0; i < n; i++)
        cout << G2[i] << " ";
    cout << endl;
    cout << "R = ";
    for (int_t i = 0; i < n; i++)
        cout << R[i] << " ";
    cout << endl;
    cout << endl;
#endif
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int_t n;
    cin >> n;
    static int_t A[LARGE], B[LARGE];
    static int_t C[LARGE];
    for (int_t i = 0; i < n; i++)
        cin >> A[i];
    poly_exp(A, n, B);
    for (int_t i = 0; i < n; i++)
        cout << B[i] << " ";

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

#include <cstring>

#include <iostream>

#include <random>

using int_t = long long int;

using std::cin;

using std::cout;

using std::endl;

const int_t LARGE = 2e6;

const int_t mod = 998244353;

const int_t g = 3;

int_t power(int_t b, int_t i) {

int_t r = 1;

if (i < 0)

i = (i % (mod - 1) + mod - 1) % (mod - 1);

while (i) {

if (i & 1)

r = r * b % mod;

b = b * b % mod;

i >>= 1;

}

return r;

}

void makeflip(int_t* arr, int_t size2) {

int_t len = (1 << size2);

arr[0] = 0;

for (int_t i = 1; i < len; i++) {

arr[i] = (arr[i >> 1] >> 1) | ((i & 1) << (size2 - 1));

}

int_t upper2n(int_t x) {

int_t r = 0;

while ((1 << r) < x)

r++;

return r;

}

template <int_t arg = 1>

void transform(int_t* A, int_t size2, int_t* flip) {

int_t len = (1 << size2);

for (int_t i = 0; i < len; i++) {

int_t r = flip[i];

if (r > i)

std::swap(A[i], A[r]);

}

for (int_t i = 2; i <= len; i *= 2) {

int_t mr = power(g, arg * (mod - 1) / i);

for (int_t j = 0; j < len; j += i) {

int_t curr = 1;

for (int_t k = 0; k < i / 2; k++) {

int_t u = A[j + k], v = curr * A[j + k + i / 2] % mod;

A[j + k] = (u + v) % mod;

A[j + k + i / 2] = (u - v + mod) % mod;

curr = curr * mr % mod;

}

void poly_inv(const int_t* A, int_t n, int_t* result) {

这里的n是模x^n

计算B(x)*A(x) = 1 mod x^n, 其中A(x)已知

假设已知A(x)*B(x) = 1 mod x^{ceil(n/2)}

假设C(x)*A(x) = 1 mod x^n

(A(x)B(x)-1)^2 = A^2(x)B^2(x)-2A(x)B(x)+1= 0

A(x)B^2(x)-2B(x)+C(x) = 0

C(x) = 2B(x)-A(x)B^2(x)

// #ifdef DEBUG

// cout << "at " << n << endl;

// #endif

if (n == 1) {

result[0] = power(A[0], -1);

return;

}

int_t next = n / 2 + n % 2;

poly_inv(A, next, result);

//次数不要选错了，应该用n次的A和B去卷

int_t size2 = upper2n(n + 2 * next + 1);

static int_t X[LARGE];

static int_t Y[LARGE];

int_t len = (1 << size2);

// 写错设置范围了！

memset(X + n, 0, sizeof(X[0]) * (len - n));

memset(Y + next, 0, sizeof(Y[0]) * (len - next));

memcpy(X, A, sizeof(A[0]) * n);

memcpy(Y, result, sizeof(result[0]) * next);

static int_t fliparr[LARGE];

makeflip(fliparr, size2);

transform<1>(X, size2, fliparr);

transform<1>(Y, size2, fliparr);

for (int_t i = 0; i < len; i++) {

X[i] = (2 * Y[i] - X[i] * Y[i] % mod * Y[i] % mod + mod) % mod;

}

transform<-1>(X, size2, fliparr);

const int_t inv = power(len, -1);

for (int_t i = 0; i < n; i++)

result[i] = X[i] * inv % mod;

#ifdef DEBUG

cout << "poly inv at " << n << endl;

cout << "result = ";

for (int_t i = 0; i < next; i++)

cout << result[i] << " ";

cout << endl;

#endif

}

int_t poly_divat(const int_t* F, const int_t* G, int_t n, int_t k) {

n次多项式F和G

计算F(x)/G(x)的k次项前系数

考虑F(x)*G(-x)/G(x)*G(-x)，分母只有偶数次项，写为C(x^2)；分子写成xA(x^2)+B(x^2)，如果k是奇数，那么递归(A,C,n,k/2)，如果k是偶数，那么递归(B,C,n,k/2)

到k<=n时直接计算

int_t size2 = upper2n(2 * n + 1);

int_t len = 1 << size2;

static int_t fliparr[LARGE];

makeflip(fliparr, size2);

static int_t T1[LARGE], T2[LARGE], T3[LARGE];

for (int_t i = 0; i < len; i++) {

if (i <= n)

T1[i] = F[i], T2[i] = G[i];

else

T1[i] = T2[i] = T3[i] = 0;

}

const int_t inv = power(len, -1);

while (k >= n) {

#ifdef DEBUG

cout << "curr at k = " << k << endl;

#endif

for (int_t i = 0; i < len; i++) {

if (i <= n) {

T3[i] = T2[i] * (i % 2 ? (mod - 1) : 1);

} else

T3[i] = 0;

}

transform(T1, size2, fliparr);

transform(T2, size2, fliparr);

transform(T3, size2, fliparr);

for (int_t i = 0; i < len; i++) {

T1[i] = T1[i] * T3[i] % mod;

T2[i] = T2[i] * T3[i] % mod;

}

transform<-1>(T1, size2, fliparr);

transform<-1>(T2, size2, fliparr);

#ifdef DEBUG

cout << "prod T1 = ";

for (int_t i = 0; i < len; i++)

cout << T1[i] * inv % mod << " ";

cout << endl;

cout << "prod T2 = ";

for (int_t i = 0; i < len; i++)

cout << T2[i] * inv % mod << " ";

cout << endl;

#endif

for (int_t i = 0; i < len; i++) {

if (i * 2 < len) {

T2[i] = T2[i * 2] * inv % mod;

} else

T2[i] = 0;

}

int_t b = k % 2;

for (int_t i = 0; i < len; i++) {

if (i % 2 == b) {

T1[i / 2] = T1[i] * inv % mod;

#ifdef DEBUG

cout << "at " << i << " assgin " << T1[i] * inv << " to "

<< i / 2 << endl;

#endif

}

#ifdef DEBUG

cout << "assign 0 to " << i << endl;

#endif

if (i > 0)

T1[i] = 0;

}

#ifdef DEBUG

cout << "finished T1 = ";

for (int_t i = 0; i < len; i++)

cout << T1[i] % mod << " ";

cout << endl;

cout << "finished T2 = ";

for (int_t i = 0; i < len; i++)

cout << T2[i] % mod << " ";

cout << endl;

#endif

k >>= 1;

}

poly_inv(T2, k + 1, T3);

// #ifdef DEBUG

// cout << "finished k = " << k << endl;

// cout << "T1 = ";

// for (int_t i = 0; i < len; i++)

// cout << T1[i] % mod << " ";

// cout << endl;

// cout << "T2 = ";

// for (int_t i = 0; i < len; i++)

// cout << T2[i] % mod << " ";

// cout << endl;

// cout << "T2 inv = ";

// for (int_t i = 0; i < len; i++)

// cout << T3[i] % mod << " ";

// cout << endl;

// #endif

int_t result = 0;

//计算结果的k次项

for (int_t i = 0; i <= k; i++) {

result = (result + T1[i] * T3[k - i] % mod) % mod;

}

return result;

}

void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {

计算n次多项式A与m次多项式B的乘积

int_t size2 = upper2n(n + m + 1);

int_t len = 1 << size2;

static int_t T1[LARGE], T2[LARGE];

for (int_t i = 0; i < len; i++) {

if (i <= n)

T1[i] = A[i];

else

T1[i] = 0;

if (i <= m)

T2[i] = B[i];

else

T2[i] = 0;

}

static int_t fliparr[LARGE];

makeflip(fliparr, size2);

transform(T1, size2, fliparr);

transform(T2, size2, fliparr);

for (int_t i = 0; i < len; i++)

T1[i] = T1[i] * T2[i] % mod;

transform<-1>(T1, size2, fliparr);

int_t inv = power(len, -1);

for (int_t i = 0; i <= n + m; i++)

C[i] = T1[i] * inv % mod;

}

int_t poly_linear_rec(const int_t* A0, const int_t* F0, int_t n, int_t k) {

计算线性递推

F[1],F[2]...F[k] 递推系数

A[0],A[1]...A[k-1] 首项

A[m]=A[m-1]*F[1]+A[m-2]*F[2]+...+A[m-k]*F[k]

static int_t T1[LARGE], T2[LARGE];

static int_t Ax[LARGE], Fx[LARGE];

Fx[0] = 0;

Ax[k] = 0;

for (int i = 1; i <= k; i++) {

Fx[i] = F0[i];

Ax[i - 1] = A0[i - 1];

}

poly_mul(Ax, k, Fx, k, T1);

T1[0] = Ax[0];

for (int i = 1; i <= k - 1; i++) {

T1[i] = (Ax[i] - T1[i] + mod) % mod;

}

for (int i = k; i <= 2 * k; i++)

T1[i] = 0;

T2[0] = 1;

for (int i = 1; i <= k; i++)

T2[i] = (mod - Fx[i]) % mod;

// #ifdef DEBUG

// cout << "T1 = ";

// for (int_t i = 0; i <= k; i++) {

// cout << T1[i] << " ";

// }

// cout << endl;

// cout << "T2 = ";

// for (int_t i = 0; i <= k; i++) {

// cout << T2[i] << " ";

// }

// cout << endl;

// #endif

return poly_divat(T1, T2, k, n);

}

void poly_log(const int_t* A, int_t n, int_t* out) {

计算log(A(x)), A(x)为n次多项式

DlogF(x) =DF(x)/F(x)

static int_t Ad[LARGE];

static int_t Finv[LARGE];

static int_t R[LARGE];

const int_t m = n - 1;

for (int_t i = 0; i <= m; i++) {

Ad[i] = A[i + 1] * (i + 1) % mod;

}

Ad[n] = 0;

poly_inv(A, n + 1, Finv);

poly_mul(Ad, m, Finv, n, R);

for (int_t i = 1; i <= n; i++) {

out[i] = R[i - 1] * power(i, -1) % mod;

}

void poly_exp(const int_t* A, int_t n, int_t* out) {

计算exp(A(x)), A(x)为n次多项式

H(x)=G(x)(1-logG(x)+A(x))

H(x)为当次递推项，G(x)为上一次递推项

if (n == 1) {

out[0] = 1;

return;

}

int_t r = n / 2 + n % 2;

poly_exp(A, r, out);

static int_t G[LARGE];

static int_t G2[LARGE];

static int_t logG[LARGE];

static int_t R[LARGE];

for (int_t i = 0; i < r; i++)

G[i] = out[i];

for (int_t i = r; i < n; i++)

G[i] = 0;

poly_log(G, n - 1, logG);

// for (int_t i = r; i < n; i++)

// logG[i] = 0;

for (int_t i = 0; i < n; i++) {

G2[i] = (mod - logG[i] + A[i]) % mod;

}

G2[0] = (G2[0] + 1) % mod;

poly_mul(G, n - 1, G2, n - 1, R);

for (int_t i = 0; i < n; i++)

out[i] = R[i];

#ifdef DEBUG

cout << "at " << n << endl;

cout << "A = ";

for (int_t i = 0; i < n; i++)

cout << A[i] << " ";

cout << endl;

cout << "G = ";

for (int_t i = 0; i < n; i++)

cout << G[i] << " ";

cout << endl;

cout << "logG = ";

for (int_t i = 0; i < n; i++)

cout << logG[i] << " ";

cout << endl;

cout << "G2 = ";

for (int_t i = 0; i < n; i++)

cout << G2[i] << " ";

cout << endl;

cout << "R = ";

for (int_t i = 0; i < n; i++)

cout << R[i] << " ";

cout << endl;

#endif

}

int main() {

std::ios::sync_with_stdio(false);

cin.tie(0), cout.tie(0);

int_t n;

cin >> n;

static int_t A[LARGE], B[LARGE];

static int_t C[LARGE];

for (int_t i = 0; i < n; i++)

cin >> A[i];

poly_exp(A, n, B);

for (int_t i = 0; i < n; i++)

cout << B[i] << " ";

return 0;

}

常系数线性递推的新做法 – 计算[x^k]P(x)/Q(x)

2021年8月12日 by officeyutong·0评论

$$ a_n=\sum_{1\le i\le k}{f_ia_{n-i}} \\ \left\{ a_0,a_1....a_{k-1} \right\} \text{已知} \\ \\ \text{设}F\left( 阅读全文..

CFGYM 102823 CCPC2018 桂林 B题 Array Modify

2021年3月4日 by officeyutong·0评论

阅读全文..

noi.ac 154 Curiosity

2019年4月22日 by officeyutong·0评论

$$ \text{设}f\left( i,j \right) \text{表示第}i\text{次扔骰子是否取到}j\text{这个数，显然这个东西的期望} 阅读全文..

洛谷4705 玩游戏

2019年4月19日 by officeyutong·0评论

$$ \text{原式}=\frac{1}{nm}\sum_{1\le k\le t}{x^k\sum_{1\le i\le n}{\sum_{1\le j\le m}{\left( a_i+b_j 阅读全文..

多项式反三角函数

2019年3月30日 by officeyutong·0评论

$$ \text{由欧拉公式得}e^{i\theta}=\cos \left( \theta \right) +i\sin \left( \theta \right) \\ 阅读全文..

多项式三角函数 & 多项式幂函数

2019年3月30日 by officeyutong·0评论

多项式三角函数

根据欧拉公式，$e^{iF(x)}=\cos(F(x))+i\sin(F(x))$,令$F(x)$为模意义下的复多项式，直接计算即可。
阅读全文..

洛谷4841 城市规划

2019年2月28日 by officeyutong·0评论

带标号无向连通图计数，使用多项式ln。

#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;cmath&gt;
#include &lt;assert.h&gt;
#include &lt;sstream&gt;
#include &lt;cstdio&gt;
typedef long long int int_t;
using std::cin;
using std::cout;
using std::endl;
//1004535809
//const int_t mod = 998244353;
const int_t mod = 1004535809;
const int_t g = 3;
int_t power(int_t base, int_t index);
int_t upper2n(int_t x);
int_t bitReverse(int_t bits, int_t size2);
template &lt;int_t arg&gt;
void transform(int_t *A, int_t size);
void poly_inv(int_t *A, int_t *inv, int_t n);
void poly_log(int_t *A, int_t n);
const int_t LARGE = 1 &lt;&lt; 22;
int_t C2(int_t x){
    return x * (x - 1) % mod * power(2,-1) % mod;
}
//4 38
 
int main()
{
//  freopen("count.in","r",stdin);
//  freopen("count.out","w",stdout);
    static int_t A[LARGE];
    static int_t fact[LARGE + 1];
    fact[0] = 1;
    int_t n;
    cin &gt;&gt; n;
    for(int_t i = 1;i &lt;= n ;i++){
        fact[i] = fact[i - 1] * i % mod;
    }
    for(int_t i = 0;i &lt;= n ;i++){
        A[i] = power(2 , i*(i-1)/2) * power(fact[i] , -1)%mod;
    }
    poly_log(A,n+1);
    for(int_t i = 0 ;i &lt;= n  ;i ++){
        A[i] = A[i] * fact[i] % mod;
    }
    cout &lt;&lt; A[n] &lt;&lt; endl;
    return 0;
}
void poly_log(int_t *A, int_t n)
{
    int_t size = upper2n(2 * n);
    static int_t inv[LARGE];
    std::fill(inv, inv + size, 0);
    poly_inv(A, inv, n);
    for (int_t i = 0; i &lt; n; i++)
    {
        A[i] = (A[i + 1] * (i + 1)) % mod;
    }
    transform&lt;1&gt;(A, size);
    transform&lt;1&gt;(inv, size);
    for (int_t i = 0; i &lt; size; i++)
    {
        A[i] = (A[i] * inv[i]) % mod;
    }
    transform&lt;-1&gt;(A, size);
    for (int_t i = n - 1; i &gt;= 1; i--)
    {
        A[i] = A[i - 1] * power(i, -1) % mod * power(size, -1) % mod;
    }
    A[0] = 0;
}
void poly_inv(int_t *A, int_t *inv, int_t n)
{
    static int_t Ax[LARGE];
    if (n == 1)
    {
        inv[0] = power(A[0], -1);
        return;
    }
    poly_inv(A, inv, n / 2 + n % 2);
    int_t size = upper2n(n * 3 - 1);
    for (int_t i = 0; i &lt; size; i++)
    {
 
        if (i &lt; n)
        {
            Ax[i] = A[i];
        }
        else
        {
            Ax[i] = 0;
        }
    }
    transform&lt;1&gt;(inv, size);
    transform&lt;1&gt;(Ax, size);
    for (int_t i = 0; i &lt; size; i++)
    {
        inv[i] = (2 * inv[i] - inv[i] * inv[i] % mod * Ax[i] % mod + mod) % mod;
    }
    transform&lt;-1&gt;(inv, size);
    for (int_t i = 0; i &lt; n; i++)
    {
        inv[i] = (inv[i] * power(size, -1)) % mod;
    }
    for (int_t i = n; i &lt; size; i++)
    {
        inv[i] = 0;
    }
}
template &lt;int_t arg &gt;
void transform(int_t *A, int_t size)
{
    int_t size2 = log2(size);
    for (int_t i = 0; i &lt; size; i++)
    {
        int_t x = bitReverse(i, size2);
        if (x &gt; i)
        {
            std::swap(A[i], A[x]);
        }
    }
    for (int_t i = 2; i &lt;= size; i *= 2)
    {
        int_t mr = power(g, arg * (mod - 1) / i);
        for (int_t j = 0; j &lt; size; j += i)
        {
            int_t curr = 1;
            for (int_t k = 0; k &lt; i / 2; k++)
            {
                int_t u = A[j + k];
                int_t t = A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (u - t + mod) % mod;
                curr = (curr * mr) % mod;
            }
        }
    }
}
 
int_t bitReverse(int_t bits, int_t size2)
{
    int_t result = 0;
    for (int_t i = 1; i &lt; size2; i++)
    {
        result |= (bits &amp; 1);
        result &lt;&lt;= 1;
        bits &gt;&gt;= 1;
    }
    return result | (bits &amp; 1);
}
int_t upper2n(int_t x)
{
    int_t result = 1;
    while (result &lt; x)
        result *= 2;
    return result;
}
int_t power(int_t base, int_t index)
{
    int_t result = 1;
    if (index &lt; 0)
    {
        index *= -1;
        base = power(base, mod - 2);
    }
    while (index)
    {
        if (index &amp; 1)
        {
            result = (result * base) % mod;
        }
        index &gt;&gt;= 1;
        base = (base * base) % mod;
    }
    return result;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

#include <iostream>

#include <algorithm>

#include <cmath>

#include <assert.h>

#include <sstream>

#include <cstdio>

typedef long long int int_t;

using std::cin;

using std::cout;

using std::endl;

//1004535809

//const int_t mod = 998244353;

const int_t mod = 1004535809;

const int_t g = 3;

int_t power(int_t base, int_t index);

int_t upper2n(int_t x);

int_t bitReverse(int_t bits, int_t size2);

template <int_t arg>

void transform(int_t *A, int_t size);

void poly_inv(int_t *A, int_t *inv, int_t n);

void poly_log(int_t *A, int_t n);

const int_t LARGE = 1 << 22;

int_t C2(int_t x){

return x * (x - 1) % mod * power(2,-1) % mod;

}

//4 38

int main()

{

// freopen("count.in","r",stdin);

// freopen("count.out","w",stdout);

static int_t A[LARGE];

static int_t fact[LARGE + 1];

fact[0] = 1;

int_t n;

cin >> n;

for(int_t i = 1;i <= n ;i++){

fact[i] = fact[i - 1] * i % mod;

}

for(int_t i = 0;i <= n ;i++){

A[i] = power(2 , i*(i-1)/2) * power(fact[i] , -1)%mod;

}

poly_log(A,n+1);

for(int_t i = 0 ;i <= n ;i ++){

A[i] = A[i] * fact[i] % mod;

}

cout << A[n] << endl;

return 0;

}

void poly_log(int_t *A, int_t n)

{

int_t size = upper2n(2 * n);

static int_t inv[LARGE];

std::fill(inv, inv + size, 0);

poly_inv(A, inv, n);

for (int_t i = 0; i < n; i++)

{

A[i] = (A[i + 1] * (i + 1)) % mod;

}

transform<1>(A, size);

transform<1>(inv, size);

for (int_t i = 0; i < size; i++)

{

A[i] = (A[i] * inv[i]) % mod;

}

transform<-1>(A, size);

for (int_t i = n - 1; i >= 1; i--)

{

A[i] = A[i - 1] * power(i, -1) % mod * power(size, -1) % mod;

}

A[0] = 0;

}

void poly_inv(int_t *A, int_t *inv, int_t n)

{

static int_t Ax[LARGE];

if (n == 1)

{

inv[0] = power(A[0], -1);

return;

}

poly_inv(A, inv, n / 2 + n % 2);

int_t size = upper2n(n * 3 - 1);

for (int_t i = 0; i < size; i++)

{

if (i < n)

{

Ax[i] = A[i];

}

else

{

Ax[i] = 0;

}

transform<1>(inv, size);

transform<1>(Ax, size);

for (int_t i = 0; i < size; i++)

{

inv[i] = (2 * inv[i] - inv[i] * inv[i] % mod * Ax[i] % mod + mod) % mod;

}

transform<-1>(inv, size);

for (int_t i = 0; i < n; i++)

{

inv[i] = (inv[i] * power(size, -1)) % mod;

}

for (int_t i = n; i < size; i++)

{

inv[i] = 0;

}

template <int_t arg >

void transform(int_t *A, int_t size)

{

int_t size2 = log2(size);

for (int_t i = 0; i < size; i++)

{

int_t x = bitReverse(i, size2);

if (x > i)

{

std::swap(A[i], A[x]);

}

for (int_t i = 2; i <= size; i *= 2)

{

int_t mr = power(g, arg * (mod - 1) / i);

for (int_t j = 0; j < size; j += i)

{

int_t curr = 1;

for (int_t k = 0; k < i / 2; k++)

{

int_t u = A[j + k];

int_t t = A[j + k + i / 2] * curr % mod;

A[j + k] = (u + t) % mod;

A[j + k + i / 2] = (u - t + mod) % mod;

curr = (curr * mr) % mod;

}

int_t bitReverse(int_t bits, int_t size2)

{

int_t result = 0;

for (int_t i = 1; i < size2; i++)

{

result |= (bits & 1);

result <<= 1;

bits >>= 1;

}

return result | (bits & 1);

}

int_t upper2n(int_t x)

{

int_t result = 1;

while (result < x)

result *= 2;

return result;

}

int_t power(int_t base, int_t index)

{

int_t result = 1;

if (index < 0)

{

index *= -1;

base = power(base, mod - 2);

}

while (index)

{

if (index & 1)

{

result = (result * base) % mod;

}

index >>= 1;

base = (base * base) % mod;

}

return result;

}

LOJ150 YT2sOJ21 挑战多项式

2019年2月26日 by officeyutong·0评论

毕竟是板子集合，不管常数了。

#include &lt;assert.h&gt;
#include &lt;algorithm&gt;
#include &lt;cmath&gt;
#include &lt;cstring&gt;
#include &lt;ctime&gt;
#include &lt;iostream&gt;
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int mod = 998244353;
const int g = 3;
const int LARGE = 1 &lt;&lt; 19;
int revs[20][LARGE + 1];

int power(int base, int index);
void transform(int* A, int len, int arg);
void poly_inv(const int* A, int n, int* result);
void poly_sqrt(const int* A, int n, int* result);
void poly_log(const int* A, int n, int* result);
void poly_exp(const int* A, int n, int* result);
void poly_power(const int* A, int n, int index, int* result);
int modSqrt(int a);
int bitRev(int base, int size2) {
    int result = 0;
    for (int i = 1; i &lt; size2; i++) {
        result |= (base &amp; 1);
        base &gt;&gt;= 1;
        result &lt;&lt;= 1;
    }
    result |= (base &amp; 1);
    return result;
}
int upper2n(int x) {
    int result = 1;
    while (result &lt; x) result *= 2;
    return result;
}
int main() {
#ifdef TIME
    auto begin = clock();
#endif
    for (int i = 0; (1 &lt;&lt; i) &lt;= LARGE; i++) {
        for (int j = 0; j &lt; LARGE; j++) {
            revs[i][j] = bitRev(j, i);
        }
    }
    static int F[LARGE + 1], A[LARGE + 1], B[LARGE + 1];
    int n, k;

    scanf("%d%d", &amp;n, &amp;k);
    for (int i = 0; i &lt;= n; i++) {
        scanf("%d", &amp;A[i]);
        F[i] = A[i];
    }
    poly_sqrt(A, n + 1, B);

#ifdef DEBUG
    cout &lt;&lt; "sqrt ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; B[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    memset(A, 0, sizeof(A));
    poly_inv(B, n + 1, A);
#ifdef DEBUG
    cout &lt;&lt; "sqrt inv ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; A[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    for (int i = n; i &gt;= 1; i--) B[i] = (int_t)A[i - 1] * power(i, -1) % mod;
    B[0] = 0;
#ifdef DEBUG
    cout &lt;&lt; "sqrt inv integrate ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; B[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    memset(A, 0, sizeof(A));
    poly_exp(B, n + 1, A);
#ifdef DEBUG
    cout &lt;&lt; "sqrt inv integrate exp ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; A[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    for (int i = 0; i &lt; n + 1; i++) {
        A[i] = (F[i] - A[i] + mod) % mod;
    }
    A[0] = (A[0] + 2 - F[0] + mod) % mod;
#ifdef DEBUG
    cout &lt;&lt; "sqrt inv integrate exp process ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; A[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    // memset(B, 0, sizeof(B));
    poly_log(A, n + 1, B);

    B[0] = 1;
#ifdef DEBUG
    cout &lt;&lt; "sqrt inv integrate exp process log +1 ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; B[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    // memset(A, 0, sizeof());
    poly_power(B, n + 1, k, A);
#ifdef DEBUG
    cout &lt;&lt; "sqrt inv integrate exp process power ";
    for (int_t i = 0; i &lt;= n; i++) cout &lt;&lt; A[i] &lt;&lt; " ";
    cout &lt;&lt; endl;
#endif
    for (int i = 0; i &lt; n; i++) {
        A[i] = (int_t)A[i + 1] * (i + 1) % mod;
        printf("%d ", A[i]);
    }
#ifdef TIME
    auto end = clock();
    cout &lt;&lt; 1.0 * (end - begin) / CLOCKS_PER_SEC &lt;&lt; endl;
#endif
    return 0;
}
//计算A(x)^index mod x^n
void poly_power(const int* A, int n, int index, int* result) {
    int size2 = upper2n(2 * n);
    static int base[LARGE + 1];
    for (int i = 0; i &lt; size2; i++) {
        if (i &lt; n)
            base[i] = A[i];
        else
            base[i] = 0;
        result[i] = 0;
    }
    result[0] = 1;
    while (index) {
        transform(base, size2, 1);
        if (index &amp; 1) {
            transform(result, size2, 1);
            for (int i = 0; i &lt; size2; i++) {
                result[i] = (int_t)result[i] * base[i] % mod;
            }
            transform(result, size2, -1);
            for (int i = 0; i &lt; size2; i++) {
                if (i &lt; n)
                    result[i] = (int_t)result[i] * power(size2, -1) % mod;
                else
                    result[i] = 0;
            }
        }
        for (int i = 0; i &lt; size2; i++)
            base[i] = (int_t)base[i] * base[i] % mod;
        transform(base, size2, -1);
        for (int i = 0; i &lt; size2; i++) {
            if (i &lt; n)
                base[i] = (int_t)base[i] * power(size2, -1) % mod;
            else
                base[i] = 0;
        }
        index &gt;&gt;= 1;
    }
}
int power(int base, int index) {
    const int phi = mod - 1;
    index = (index % phi + phi) % phi;
    base = (base % mod + mod) % mod;
    int result = 1;
    while (index) {
        if (index &amp; 1) result = (int_t)result * base % mod;
        base = (int_t)base * base % mod;
        index &gt;&gt;= 1;
    }
    return result;
}
void transform(int* A, int len, int arg) {
    int size2 = log2(len);
    for (int i = 0; i &lt; len; i++) {
        int x = revs[size2][i];
        if (x &gt; i) std::swap(A[i], A[x]);
    }
    for (int i = 2; i &lt;= len; i *= 2) {
        int mr = power(g, (int_t)arg * (mod - 1) / i);
        for (int j = 0; j &lt; len; j += i) {
            int curr = 1;
            for (int k = 0; k &lt; i / 2; k++) {
                int u = A[j + k];
                int t = (int_t)A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (u - t + mod) % mod;
                curr = (int_t)curr * mr % mod;
            }
        }
    }
}
//计算多项式A在模x^n下的逆元
// C(x)&lt;-2B(x)-A(x)B^2(x)
void poly_inv(const int* A, int n, int* result) {
    if (n == 1) {
        result[0] = power(A[0], -1);
        return;
    }
    poly_inv(A, n / 2 + n % 2, result);
    static int temp[LARGE + 1];
    int size2 = upper2n(3 * n + 1);
    for (int i = 0; i &lt; size2; i++) {
        if (i &lt; n)
            temp[i] = A[i];
        else
            temp[i] = 0;
    }
    transform(temp, size2, 1);
    transform(result, size2, 1);
    for (int i = 0; i &lt; size2; i++) {
        result[i] =
            ((int_t)2 * result[i] % mod -
             (int_t)temp[i] * result[i] % mod * result[i] % mod + 2 * mod) %
            mod;
    }
    transform(result, size2, -1);
    for (int i = 0; i &lt; size2; i++) {
        if (i &lt; n) {
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        } else {
            result[i] = 0;
        }
    }
}
int modSqrt(int a) {
    const int_t b = 3;
    // mod-1=2^s*t
    int s = 23, t = 119;
    int x = power(a, (t + 1) / 2);
    int e = power(a, t);
    int k = 1;
    while (k &lt; s) {
        if (power(e, 1 &lt;&lt; (s - k - 1)) != 1) {
            x = (int_t)x * power(b, (1 &lt;&lt; (k - 1)) * t) % mod;
        }
        e = (int_t)power(a, -1) * x % mod * x % mod;
        k++;
    }
    return x;
}
//计算多项式开根
void poly_sqrt(const int* A, int n, int* result) {
    if (n == 1) {
        int p = modSqrt(A[0]);
        result[0] = std::min(p, mod - p);
        return;
    }
    poly_sqrt(A, n / 2 + n % 2, result);
    int size2 = upper2n(3 * n);
    static int Ax[LARGE + 1], pInv[LARGE];
    for (int i = 0; i &lt; size2; i++) {
        if (i &lt; n) {
            Ax[i] = A[i];
        } else {
            Ax[i] = 0;
        }
        pInv[i] = 0;
    }
    poly_inv(result, n, pInv);
    transform(Ax, size2, 1);
    transform(result, size2, 1);
    transform(pInv, size2, 1);
    const int inv2 = power(2, -1);
    for (int i = 0; i &lt; size2; i++) {
        result[i] = (result[i] -
                     ((int_t)result[i] * result[i] % mod - Ax[i] + mod) % mod *
                         inv2 % mod * pInv[i] % mod +
                     mod) %
                    mod;
    }
    transform(result, size2, -1);
    for (int i = 0; i &lt; size2; i++) {
        if (i &lt; n)
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        else
            result[i] = 0;
    }
}
void poly_log(const int* A, int n, int* result) {
    int size2 = upper2n(2 * n);
    static int Ad[LARGE + 1];
    for (int i = 0; i &lt; size2; i++) {
        if (i &lt; n) {
            Ad[i] = (int_t)(i + 1) * A[i + 1] % mod;

        } else {
            Ad[i] = 0;
        }
        result[i] = 0;
    }
    transform(Ad, size2, 1);
    poly_inv(A, n, result);
    transform(result, size2, 1);
    for (int i = 0; i &lt; size2; i++) {
        result[i] = (int_t)result[i] * Ad[i] % mod;
    }
    transform(result, size2, -1);
    for (int i = 0; i &lt; size2; i++)
        if (i &lt; n)
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        else
            result[i] = 0;
    for (int i = n - 1; i &gt;= 1; i--) {
        result[i] = (int_t)result[i - 1] * power(i, -1) % mod;
    }
    result[0] = 0;
}
void poly_exp(const int* A, int n, int* result) {
    if (n == 1) {
        assert(A[0] == 0);
        result[0] = 1;
        return;
    }
    poly_exp(A, n / 2 + n % 2, result);
    static int G0[LARGE + 1], Ax[LARGE + 1];
    int size2 = upper2n(2 * n);
    poly_log(result, n, G0);
    for (int_t i = 0; i &lt; size2; i++) {
        if (i &lt; n)
            Ax[i] = A[i];
        else
            Ax[i] = 0;
    }
    transform(Ax, size2, 1);
    transform(G0, size2, 1);
    transform(result, size2, 1);
    for (int i = 0; i &lt; size2; i++)
        result[i] =
            (result[i] - (int_t)result[i] * (G0[i] - Ax[i] + mod) % mod + mod) %
            mod;
    transform(result, size2, -1);
    for (int i = 0; i &lt; size2; i++)
        if (i &lt; n)
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        else
            result[i] = 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

#include <assert.h>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

using int_t = long long int;

using std::cin;

using std::cout;

using std::endl;

const int mod = 998244353;

const int g = 3;

const int LARGE = 1 << 19;

int revs[20][LARGE + 1];

int power(int base, int index);

void transform(int* A, int len, int arg);

void poly_inv(const int* A, int n, int* result);

void poly_sqrt(const int* A, int n, int* result);

void poly_log(const int* A, int n, int* result);

void poly_exp(const int* A, int n, int* result);

void poly_power(const int* A, int n, int index, int* result);

int modSqrt(int a);

int bitRev(int base, int size2) {

int result = 0;

for (int i = 1; i < size2; i++) {

result |= (base & 1);

base >>= 1;

result <<= 1;

}

result |= (base & 1);

return result;

}

int upper2n(int x) {

int result = 1;

while (result < x) result *= 2;

return result;

}

int main() {

#ifdef TIME

auto begin = clock();

#endif

for (int i = 0; (1 << i) <= LARGE; i++) {

for (int j = 0; j < LARGE; j++) {

revs[i][j] = bitRev(j, i);

}

static int F[LARGE + 1], A[LARGE + 1], B[LARGE + 1];

int n, k;

scanf("%d%d", &n, &k);

for (int i = 0; i <= n; i++) {

scanf("%d", &A[i]);

F[i] = A[i];

}

poly_sqrt(A, n + 1, B);

#ifdef DEBUG

cout << "sqrt ";

for (int_t i = 0; i <= n; i++) cout << B[i] << " ";

cout << endl;

#endif

memset(A, 0, sizeof(A));

poly_inv(B, n + 1, A);

#ifdef DEBUG

cout << "sqrt inv ";

for (int_t i = 0; i <= n; i++) cout << A[i] << " ";

cout << endl;

#endif

for (int i = n; i >= 1; i--) B[i] = (int_t)A[i - 1] * power(i, -1) % mod;

B[0] = 0;

#ifdef DEBUG

cout << "sqrt inv integrate ";

for (int_t i = 0; i <= n; i++) cout << B[i] << " ";

cout << endl;

#endif

memset(A, 0, sizeof(A));

poly_exp(B, n + 1, A);

#ifdef DEBUG

cout << "sqrt inv integrate exp ";

for (int_t i = 0; i <= n; i++) cout << A[i] << " ";

cout << endl;

#endif

for (int i = 0; i < n + 1; i++) {

A[i] = (F[i] - A[i] + mod) % mod;

}

A[0] = (A[0] + 2 - F[0] + mod) % mod;

#ifdef DEBUG

cout << "sqrt inv integrate exp process ";

for (int_t i = 0; i <= n; i++) cout << A[i] << " ";

cout << endl;

#endif

// memset(B, 0, sizeof(B));

poly_log(A, n + 1, B);

B[0] = 1;

#ifdef DEBUG

cout << "sqrt inv integrate exp process log +1 ";

for (int_t i = 0; i <= n; i++) cout << B[i] << " ";

cout << endl;

#endif

// memset(A, 0, sizeof());

poly_power(B, n + 1, k, A);

#ifdef DEBUG

cout << "sqrt inv integrate exp process power ";

for (int_t i = 0; i <= n; i++) cout << A[i] << " ";

cout << endl;

#endif

for (int i = 0; i < n; i++) {

A[i] = (int_t)A[i + 1] * (i + 1) % mod;

printf("%d ", A[i]);

}

#ifdef TIME

auto end = clock();

cout << 1.0 * (end - begin) / CLOCKS_PER_SEC << endl;

#endif

return 0;

}

//计算A(x)^index mod x^n

void poly_power(const int* A, int n, int index, int* result) {

int size2 = upper2n(2 * n);

static int base[LARGE + 1];

for (int i = 0; i < size2; i++) {

if (i < n)

base[i] = A[i];

else

base[i] = 0;

result[i] = 0;

}

result[0] = 1;

while (index) {

transform(base, size2, 1);

if (index & 1) {

transform(result, size2, 1);

for (int i = 0; i < size2; i++) {

result[i] = (int_t)result[i] * base[i] % mod;

}

transform(result, size2, -1);

for (int i = 0; i < size2; i++) {

if (i < n)

result[i] = (int_t)result[i] * power(size2, -1) % mod;

else

result[i] = 0;

}

for (int i = 0; i < size2; i++)

base[i] = (int_t)base[i] * base[i] % mod;

transform(base, size2, -1);

for (int i = 0; i < size2; i++) {

if (i < n)

base[i] = (int_t)base[i] * power(size2, -1) % mod;

else

base[i] = 0;

}

index >>= 1;

}

int power(int base, int index) {

const int phi = mod - 1;

index = (index % phi + phi) % phi;

base = (base % mod + mod) % mod;

int result = 1;

while (index) {

if (index & 1) result = (int_t)result * base % mod;

base = (int_t)base * base % mod;

index >>= 1;

}

return result;

}

void transform(int* A, int len, int arg) {

int size2 = log2(len);

for (int i = 0; i < len; i++) {

int x = revs[size2][i];

if (x > i) std::swap(A[i], A[x]);

}

for (int i = 2; i <= len; i *= 2) {

int mr = power(g, (int_t)arg * (mod - 1) / i);

for (int j = 0; j < len; j += i) {

int curr = 1;

for (int k = 0; k < i / 2; k++) {

int u = A[j + k];

int t = (int_t)A[j + k + i / 2] * curr % mod;

A[j + k] = (u + t) % mod;

A[j + k + i / 2] = (u - t + mod) % mod;

curr = (int_t)curr * mr % mod;

}

//计算多项式A在模x^n下的逆元

// C(x)<-2B(x)-A(x)B^2(x)

void poly_inv(const int* A, int n, int* result) {

if (n == 1) {

result[0] = power(A[0], -1);

return;

}

poly_inv(A, n / 2 + n % 2, result);

static int temp[LARGE + 1];

int size2 = upper2n(3 * n + 1);

for (int i = 0; i < size2; i++) {

if (i < n)

temp[i] = A[i];

else

temp[i] = 0;

}

transform(temp, size2, 1);

transform(result, size2, 1);

for (int i = 0; i < size2; i++) {

result[i] =

((int_t)2 * result[i] % mod -

(int_t)temp[i] * result[i] % mod * result[i] % mod + 2 * mod) %

mod;

}

transform(result, size2, -1);

for (int i = 0; i < size2; i++) {

if (i < n) {

result[i] = (int_t)result[i] * power(size2, -1) % mod;

} else {

result[i] = 0;

}

int modSqrt(int a) {

const int_t b = 3;

// mod-1=2^s*t

int s = 23, t = 119;

int x = power(a, (t + 1) / 2);

int e = power(a, t);

int k = 1;

while (k < s) {

if (power(e, 1 << (s - k - 1)) != 1) {

x = (int_t)x * power(b, (1 << (k - 1)) * t) % mod;

}

e = (int_t)power(a, -1) * x % mod * x % mod;

k++;

}

return x;

}

//计算多项式开根

void poly_sqrt(const int* A, int n, int* result) {

if (n == 1) {

int p = modSqrt(A[0]);

result[0] = std::min(p, mod - p);

return;

}

poly_sqrt(A, n / 2 + n % 2, result);

int size2 = upper2n(3 * n);

static int Ax[LARGE + 1], pInv[LARGE];

for (int i = 0; i < size2; i++) {

if (i < n) {

Ax[i] = A[i];

} else {

Ax[i] = 0;

}

pInv[i] = 0;

}

poly_inv(result, n, pInv);

transform(Ax, size2, 1);

transform(result, size2, 1);

transform(pInv, size2, 1);

const int inv2 = power(2, -1);

for (int i = 0; i < size2; i++) {

result[i] = (result[i] -

((int_t)result[i] * result[i] % mod - Ax[i] + mod) % mod *

inv2 % mod * pInv[i] % mod +

mod) %

mod;

}

transform(result, size2, -1);

for (int i = 0; i < size2; i++) {

if (i < n)

result[i] = (int_t)result[i] * power(size2, -1) % mod;

else

result[i] = 0;

}

void poly_log(const int* A, int n, int* result) {

int size2 = upper2n(2 * n);

static int Ad[LARGE + 1];

for (int i = 0; i < size2; i++) {

if (i < n) {

Ad[i] = (int_t)(i + 1) * A[i + 1] % mod;

} else {

Ad[i] = 0;

}

result[i] = 0;

}

transform(Ad, size2, 1);

poly_inv(A, n, result);

transform(result, size2, 1);

for (int i = 0; i < size2; i++) {

result[i] = (int_t)result[i] * Ad[i] % mod;

}

transform(result, size2, -1);

for (int i = 0; i < size2; i++)

if (i < n)

result[i] = (int_t)result[i] * power(size2, -1) % mod;

else

result[i] = 0;

for (int i = n - 1; i >= 1; i--) {

result[i] = (int_t)result[i - 1] * power(i, -1) % mod;

}

result[0] = 0;

}

void poly_exp(const int* A, int n, int* result) {

if (n == 1) {

assert(A[0] == 0);

result[0] = 1;

return;

}

poly_exp(A, n / 2 + n % 2, result);

static int G0[LARGE + 1], Ax[LARGE + 1];

int size2 = upper2n(2 * n);

poly_log(result, n, G0);

for (int_t i = 0; i < size2; i++) {

if (i < n)

Ax[i] = A[i];

else

Ax[i] = 0;

}

transform(Ax, size2, 1);

transform(G0, size2, 1);

transform(result, size2, 1);

for (int i = 0; i < size2; i++)

result[i] =

(result[i] - (int_t)result[i] * (G0[i] - Ax[i] + mod) % mod + mod) %

mod;

transform(result, size2, -1);

for (int i = 0; i < size2; i++)

if (i < n)

result[i] = (int_t)result[i] * power(size2, -1) % mod;

else

result[i] = 0;

}

标签： 多项式

多项式三角函数

标签：多项式