#935822 (C++17) No.2575 Almost Increasing Sequence

提出ソース

結果

問題	No.2575 Almost Increasing Sequence
ユーザー	chineristAC
提出日時	2023-12-03 05:29:57
言語	C++17 (gcc 12.3.0 + boost 1.83.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
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8,015 ms 8,080 KB
testcase_01	AC	8,232 ms 8,080 KB
testcase_02	AC	8,222 ms 8,080 KB
testcase_03	AC	8,266 ms 8,080 KB
testcase_04	AC	8,305 ms 8,080 KB
testcase_05	AC	8,271 ms 8,080 KB
testcase_06	AC	8,260 ms 8,080 KB
testcase_07	AC	8,256 ms 8,080 KB
testcase_08	AC	8,244 ms 8,080 KB
testcase_09	AC	8,244 ms 8,080 KB
testcase_10	AC	8,249 ms 8,080 KB
testcase_11	AC	8,257 ms 8,080 KB
testcase_12	AC	8,262 ms 8,080 KB
testcase_13	AC	8,328 ms 8,080 KB
testcase_14	AC	8,312 ms 8,080 KB
testcase_15	AC	8,244 ms 8,080 KB
testcase_16	AC	8,213 ms 8,080 KB
testcase_17	AC	8,236 ms 8,080 KB
testcase_18	AC	8,204 ms 8,080 KB
testcase_19	AC	8,227 ms 8,080 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// -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 << " ";
    }
  }

  



    
  
}

yukicoder

結果

テストケース

ソースコード