Submission #69187129

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;

int mod = 998244353;

// (a^p)%mod の long long 内計算（法<2^31.5に限る）
long long power_mod(long long a, long long p) {
  if (p==0) return 1LL;
  if (p&1LL) {
    return (power_mod(a,p-1)*a)%mod;
  } else {
    long long tmp = power_mod(a,p>>1);
    return tmp*tmp%mod;
  }
}

// mod上での逆数計算（法<2^31.5に限る）
long long inverse(long long a) {
  return power_mod(a,mod-2);
}

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, a, b, c;
  cin >> n >> a >> b >> c;

  int mod = 998244353;

  //////////////// 出力変数定義 ////////////////

  int result1, result2;

  //////////////////// 処理 ////////////////////

  // n!までの階乗を用意
  vector<long long> factorial(n+1,0);
  factorial.at(0) = 1;
  for (int i=1; i<=n; i++) {
    factorial.at(i) = factorial.at(i-1)*i%mod;
  }

  // 形式的べき級数用のvector
  vector<int> pa(n+1,0);
  vector<int> pb(n+1,0);
  vector<int> pc(n+1,0);

  // それぞれの箱の中で条件を満たす入れ方を数える
  for (int i=0; i<=n; i+=a) {
    pa.at(i) = 1;
  }
  for (int i=0; i<=n; i+=b) {
    pb.at(i) = 1;
  }
  for (int i=0; i<=n; i+=c) {
    pc.at(i) = 1;
  }

  // 3つを畳み込んで、n次の係数が答え
  vector<int> tmp1 = convolution<998244353>(pa,pb);
  tmp1.resize(n+1);
  vector<int> p1 = convolution<998244353>(tmp1,pc);
  p1.resize(n+1);
  result1 = p1.at(n);

  // n!/(na!*nb!*nc!)をかけたいので、畳み込む前に個数の階乗で割った状態を作る
  for (int i=0; i<=n; i+=a) {
    pa.at(i) *= inverse(factorial.at(i));
  }
  for (int i=0; i<=n; i+=b) {
    pb.at(i) *= inverse(factorial.at(i));
  }
  for (int i=0; i<=n; i+=c) {
    pc.at(i) *= inverse(factorial.at(i));
  }

  // 3つを畳み込んで、n次の係数にn!をかけたものが答え
  vector<int> tmp2 = convolution<998244353>(pa,pb);
  tmp2.resize(n+1);
  vector<int> p2 = convolution<998244353>(tmp2,pc);
  p2.resize(n+1);
  result2 = p2.at(n)*factorial.at(n)%mod;

  //////////////////// 出力 ////////////////////

  cout << result1 << endl;
  cout << result2 << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result