Submission #33934208

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll gcd(int a,int b){ return b == 0? a: gcd(b,a%b);}

map<int,mint> dp[60][60]; // dp[选最小i个][最大的环为j] = {lcm, count}
mint fac[100] = {1};
mint ifac[100];
mint binom(int n,int m) { return fac[n] * ifac[m] * ifac[n-m];}

int main(){
  rep(i,1,51) fac[i] = fac[i-1] * i;
  ifac[50] = fac[50].inv();
  per(i,0,50) ifac[i] = ifac[i+1] * (i+1);

  int n = read();
  int k = read();
  dp[0][0][1] = 1;
  rep(i,1,n+1) rep(j,1,i+1){
    mint invj = mint(j).inv();
    rep(t,1,n+1){
      int oldi = i - j*t; // [i - j*t][<j]
      if(oldi < 0) break;
      rep(k,0,j) for(auto [lcm,cnt]: dp[oldi][k]){
        int newlcm = lcm * j / gcd(lcm,j);
        dp[i][j][newlcm] += cnt * binom(n-oldi,j*t) * fac[j*t] * ifac[t] * invj.pow(t);
      }
    }
  }
  mint ans = 0;
  rep(j,1,n+1) for(auto [lcm,cnt]:dp[n][j]) ans += cnt * mint(lcm).pow(k);
  printf("%d\n",ans.val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result