Submission #366711

#	Time	Username	Problem	Language	Result	Execution time	Memory
366711		Kevin_Zhang_TW	Asceticism (JOI18_asceticism)	C++17	100 / 100	30 ms	2796 KiB

asceticism

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, p = 1e9 + 7;

int n, k;
ll fa[MAX_N], fai[MAX_N], inv[MAX_N];

void init() {
	for (int i : {0, 1})
		fa[i] = fai[i] = inv[i] = 1;
	for (int i = 2;i <= n;++i) {
		fa[i] = fa[i-1] * i % p;
		inv[i] = (p - p / i) * inv[p % i] % p;
		fai[i] = inv[i] * fai[i-1] % p;
	}
}

ll C(int N, int M) { return N < M ? 0 : fa[N] * fai[M] % p * fai[N - M] % p; }

ll bin_pow(ll v, ll t) {
	ll res = 1;
	for (;t;t>>=1, v = v * v % p)
		if (t&1) res = res * v % p;
	return res;
}

// The problem is calculate # permutation P that
// # P_i < P_{i-1} = K
//

ll ginv(ll v) { return bin_pow(v, p - 2); }

// area of N dimension sum(X_i) <= K equals to K^N / N!
// if K <= sum(Y) < K+1
// it means that the number of X_i < X_{i-1} = K

// the area of sum(Y) < a
ll area(ll sum) {
	return bin_pow(sum, n) * fai[n] % p ;
}

ll calsum(int a) {
	ll res = 0;
	for (int i = 0;i <= n;++i) {
		if (i > a) break;
		ll si = i & 1 ? -1 : 1;
		res += si * area(a - i) * C(n, i) % p;
	}
	res %= p;
	if (res < 0) res += p;
	return res;
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);

	cin >> n >> k; 
	
	--k;

	init();

	ll all = calsum(n), ok = calsum(k + 1) - calsum(k) ;

	ll res = ok * ginv(all) % p;

	if (res < 0) res += p;

	res = res * fa[n] % p;

	// res is the posibility

	DE(all, ok, fa[n]);

	cout << res << '\n';

}

Compilation message (stderr)

asceticism.cpp: In function 'int32_t main()':
asceticism.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
asceticism.cpp:88:2: note: in expansion of macro 'DE'
   88 |  DE(all, ok, fa[n]);
      |  ^~

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 51 / 51