Submission #38141401

---

Source Code Expand

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

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}
const int T=100;
vector<mint> fac;
vector<mint> ifac;
mint binom(int n,int m){return (n<m or m<0)?0:(fac[n] * ifac[n-m] * ifac[m]);}

 // 对n 拆分, 上一个拆分的大小为last, 这次比last大
 mint dfs(int n,int K, int last, vector<pair<int, int>> &v) {
   if (n == 0) {
     mint ans = 1;
     rep(i,0,size(v)){
       auto [cyc1, num1] = v[i]; // 环大小, 个数
       ans /= fac[num1] * (mint{cyc1}.pow(num1)); // 清除轮换等价
       ans *= mint{K}.pow(num1); // K^m = K^{sum num}
       ans *= mint{2}.pow(cyc1 / 2 * num1 + cyc1 * num1 * (num1 - 1) / 2); // c[i]/2 + sum gcd(num1,num1)
       rep(j,0,i) {
         auto [cyc2, num2] = v[j];
         ans *= mint{2}.pow(gcd(cyc1, cyc2) * num1 * num2);
       }
     }
     return ans;
   }else{
     mint ans = 0;
     rep(nxt,last+1,n+1) for (int i = 1; nxt * i <= n; i++) { // 拆分 i个 nxt大小的环
       v.push_back({nxt, i});
       ans += dfs(n-nxt*i, K, nxt, v);
       v.pop_back();
     }
     return ans;
   }
 }

 mint f(int n,int k){ // n点 值[1..k] 方案数
   vector<pair<int, int>> v; // {环大小, 个数}
   return dfs(n,k,0,v);
 }

 int main() {
   int n=read();
   int K=read();
   mint::set_mod(read());
   fac.assign(T+1,1);
   rep(i,1,T+1) fac[i] = fac[i - 1] * i;
   ifac.resize(T+1);
   ifac[T] = fac[T].inv();
   per(i,0,T) ifac[i] = ifac[i + 1] * (i + 1);

   mint ans = 0;
   rep(k,1,K+1) ans+=f(n,k)*binom(K, k)*(((K-k)&1)?-1:1);//容斥ans[==K]=sum binom(K,i)(-1)^{K-i}f(<=i)
   printf("%d\n",ans.val());
   return 0;
 }

Submission Info

Compile Error

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

Judge Result