結果
| 問題 |
No.2575 Almost Increasing Sequence
|
| コンテスト | |
| ユーザー |
 chineristAC
|
| 提出日時 | 2023-12-03 05:29:57 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 8,328 ms / 10,000 ms |
| コード長 | 6,021 bytes |
| コンパイル時間 | 5,934 ms |
| コンパイル使用メモリ | 232,336 KB |
| 実行使用メモリ | 8,080 KB |
| スコア | 600,000 |
| 最終ジャッジ日時 | 2023-12-03 05:33:10 |
| 合計ジャッジ時間 | 179,952 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 19 |
ソースコード
// -fsanitize=undefined,
// #define _GLIBCXX_DEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <chrono>
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;
#define rep(i,n) for (int i=0;i<n;i+=1)
#define rrep(i,n) for (int i=n-1;i>-1;i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n";
template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<class T>
bool chmin(T &a, T b){
if (a>b){
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b){
if (a<b){
a = b;
return true;
}
return false;
}
template<class T>
T sum(vec<T> x){
T res=0;
for (auto e:x){
res += e;
}
return res;
}
template<class T>
void printv(vec<T> x){
for (auto e:x){
cout<<e<<" ";
}
cout<<endl;
}
template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& A){
os << "(" << A.first <<", " << A.second << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& S){
os << "set{";
for (auto a:S){
os << a;
auto it = S.find(a);
it++;
if (it!=S.end()){
os << ", ";
}
}
os << "}";
return os;
}
using mint = modint998244353;
ostream& operator<<(ostream& os, const mint& a){
os << a.val();
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vec<T>& A){
os << "[";
rep(i,A.size()){
os << A[i];
if (i!=A.size()-1){
os << ", ";
}
}
os << "]" ;
return os;
}
const int M = 100000;
mint g1[M],g2[M],inverse[M];
void init_mint(){
g1[0] = 1; g1[1] = 1;
g2[0] = 1; g2[1] = 1;
inverse[1] = 1;
for (int n=2;n<M;n++){
g1[n] = g1[n-1] * n;
inverse[n] = (-inverse[998244353%n]) * (998244353/n);
g2[n] = inverse[n] * g2[n-1];
}
}
mint comb(int n,int r){
if (r < 0 || n < r) return 0;
return g1[n] * g2[r] * g2[n-r];
}
vector<mint> sub_solve(int N,int K,int p,int q,int r){
/*
0 <= a1 <= a2 <= a3 <= N を満たす a1,a2,a3 に対する
a1^p/(a1!)^2 * a2^q/((a2+1)!)^2 * a3^(r+K)/((a3+2)!)^2
の総和を a1+a2+a3 ごとに求める
*/
vector<vector<mint>> base_f(3,vector<mint>(N+1,0));
for (int i=1;i<=N;i++){
base_f[0][i] = mint(i).pow(p) * g2[i] * g2[i];
base_f[1][i] = mint(i).pow(q) * g2[i+1] * g2[i+1];
base_f[2][i] = mint(i).pow(r+K) * g2[i+2] * g2[i+2];
}
auto calc = [&](auto self,int l,int r)->vector<vector<mint>> {
if (r-l==1){
return {{base_f[0][l]*base_f[1][l]},{base_f[1][l]*base_f[2][l]},{base_f[0][l]*base_f[1][l]*base_f[2][l]}};
}
int m = (l+r)>>1;
auto left = self(self,l,m);
auto right = self(self,m,r);
vector<vector<mint>> res(3);
res[0].resize(2*(r-l)-1); res[1].resize(2*(r-l)-1); res[2].resize(3*(r-l)-2);
{
int LS = left[0].size(), RS = right[0].size();
for (int i=0;i<LS;i++){
res[0][i] += left[0][i];
}
for (int i=0;i<RS;i++){
res[0][i+2*(m-l)] += right[0][i];
}
vector<mint> f = {base_f[0].begin()+l,base_f[0].begin()+m};
vector<mint> g = {base_f[1].begin()+m,base_f[1].begin()+r};
auto h = convolution(f,g);
for (int i=0;i<int(h.size());i++){
res[0][i+m-l] += h[i];
}
}
{
int LS = left[1].size(), RS = right[1].size();
for (int i=0;i<LS;i++){
res[1][i] += left[1][i];
}
for (int i=0;i<RS;i++){
res[1][i+2*(m-l)] += right[1][i];
}
vector<mint> f = {base_f[1].begin()+l,base_f[1].begin()+m};
vector<mint> g = {base_f[2].begin()+m,base_f[2].begin()+r};
auto h = convolution(f,g);
for (int i=0;i<int(h.size());i++){
res[1][i+m-l] += h[i];
}
}
{
for (int i=0;i<int(left[2].size());i++){
res[2][i] += left[2][i];
}
for (int i=0;i<int(right[2].size());i++){
res[2][i+3*(m-l)] += right[2][i];
}
vector<mint> f = {base_f[0].begin()+l,base_f[0].begin()+m};
auto h = convolution(f,right[1]);
for (int i=0;i<int(h.size());i++){
res[2][i+2*(m-l)] += h[i];
}
vector<mint> g = {base_f[2].begin()+m,base_f[2].begin()+r};
h = convolution(left[0],g);
for (int i=0;i<int(h.size());i++){
res[2][i+(m-l)] += h[i];
}
}
return res;
};
auto res = calc(calc,0,N+1);
auto ans = res[2];
ans.resize(N+1);
return ans;
}
using S = map<tuple<int,int,int>,mint>;
S calc_mul(S A,S B){
S C = {};
for (auto [a_ijk,a_val]:A){
for (auto [b_ijk,b_val]:B){
auto [a,b,c] = a_ijk;
auto [d,e,f] = b_ijk;
tuple<int,int,int> nxt = {a+d,b+e,c+f};
C[nxt];
C[nxt] += a_val * b_val;
}
}
return C;
}
vector<mint> solve(int N,int K){
S A0,A1,A2;
A0[{0,0,1}] = 1; A0[{0,1,0}] = -1; A0[{0,0,0}] = 1;
A1[{0,0,1}] = 1; A1[{1,0,0}] = -1; A1[{0,0,0}] = 2;
A2[{0,1,0}] = 1; A2[{1,0,0}] = -1; A2[{0,0,0}] = 1;
S B = calc_mul(A0,calc_mul(A1,A2));
B = calc_mul(B,B);
vector<mint> res(N+1,0);
for (auto [ijk,val]:B){
if (val == 0) continue;
auto [p,q,r] = ijk;
auto tmp = sub_solve(N,K,p,q,r);
for (int i=0;i<=N;i++){
res[i] += tmp[i] * val;
}
}
for (int i=0;i<=N;i++){
res[i] *= g1[i] * g1[i];
}
return res;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
init_mint();
int K;
cin>>K;
int N = 30000;
auto res = solve(N,K);
cout << N << endl;
for (int i=1;i<=N;i++){
cout << res[i];
if (i == N){
cout << "\n";
}
else{
cout << " ";
}
}
}