1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 `#include using namespace std; #define rep(i,a,n) for (int i=a;i=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector VI; typedef long long ll; typedef pair PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=251000; const ll inf=1000000000001000000ll; vector dp[N]; int n; ll k; void init() { dp[1].pb(1); for (int i=2;i<=n;i++) { ll w=0; bool full=SZ(dp[i-1])==(ll)(i-1)*(i-2)/2+1; for (int j=0;j<=(ll)i*(i-1)/2;j++) { if (j>=SZ(dp[i-1])&&!full) break; if (j=i) w-=dp[i-1][j-i]; if (w>inf) break; dp[i].pb(w); } } } ll count(int n,ll k) { if (n==0) return k==0; k=min(k,(ll)n*(n-1)/2-k); if (k<0) return 0; if (k>=SZ(dp[n])) return inf; else return dp[n][k]; } set s; void gao(int n,ll inv) { for (int i=0;i