oj.uz

Submission #712810

# Submission time Handle Problem Language Result Execution time Memory
712810 2023-03-20T06:59:41 Z ymm Asceticism (JOI18_asceticism) C++17
4 / 100
 600 ms 7764 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int mod = 1e9+7;

ll pw(ll x, ll y)
{
	ll ans = 1;
	while (y) {
		if (y%2)
			ans = ans*x % mod;
		x = x*x % mod;
		y /= 2;
	}
	return ans;
}
ll inv(ll x) { return pw(x, mod-2); }

const int N = 100'010;
ll fct[N], fcti[N];

void init()
{
	fct[0] = 1;
	Loop (i,1,N)
		fct[i] = fct[i-1] * i % mod;
	fcti[N-1] = inv(fct[N-1]);
	LoopR (i,1,N)
		fcti[i-1] = fcti[i] * i % mod;
}

ll C(int n, int r)
{
	if (r < 0 || n < r)
		return 0;
	return fct[n] * fcti[r] % mod * fcti[n-r] % mod;
}

typedef vector<int> poly;
typedef unsigned long long ull;

#define MOD(x) ((x) = ((x) >= mod? (x) - mod: x))

poly karatsuba(poly a, poly b)
{
	int n = a.size();
	if (n <= 26) {
		poly ans(2*n-1);
		vector<ull> ansl(2*n-1);
		Loop (i,0,n) Loop (j,0,n/2)
			ansl[i+j] += (ull)a[i] * b[j];
		Loop (i,0,2*n-1)
			ansl[i] %= mod;
		Loop (i,0,n) Loop (j,n/2,n)
			ansl[i+j] += (ull)a[i] * b[j];
		Loop (i,0,2*n-1)
			ans[i] = ansl[i] % mod;
		return ans;
	}
	poly a12((n+1)/2), a2((n+1)/2);
	poly b12((n+1)/2), b2((n+1)/2);
	Loop (i,0,n/2) {
		a12[i] += a[i];
		b12[i] += b[i];
	}
	Loop (i,n/2,n) {
		a12[i-n/2] += a[i];
		a2[i-n/2] += a[i];
		b12[i-n/2] += b[i];
		b2[i-n/2] += b[i];
		MOD(a12[i-n/2]);
		MOD(b12[i-n/2]);
	}
	a.resize(n/2);
	b.resize(n/2);
	poly ans, ans12, ans2;
	ans = karatsuba(a, b);
	ans12 = karatsuba(a12, b12);
	ans2 = karatsuba(a2, b2);
	Loop (i,0,ans.size()) {
		ans12[i] += mod - ans[i];
		MOD(ans12[i]);
	}
	ans.resize(2*n-1);
	Loop (i,0,ans2.size()) {
		ans[i+2*(n/2)] += ans2[i];
		ans12[i] += mod - ans2[i];
		MOD(ans[i+2*(n/2)]);
		MOD(ans12[i]);
	}
	Loop (i,0,ans12.size()) {
		ans[i+n/2] += ans12[i];
		MOD(ans[i+n/2]);
	}
	return ans;
}

vector<int> stir;

void init_stir(int m)
{
	poly A(N), B(N);
	Loop (i,0,N) {
		A[i] = pw(i, m) * fcti[i] % mod;
		B[i] = i%2? mod-fcti[i]: fcti[i];
	}
	stir = karatsuba(A, B);
	stir.resize(N);
	Loop (i,0,N)
		stir[i] = fct[i] * stir[i] % mod;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	ll a, b;
	cin >> b >> a;
	init();
	init_stir(b);
	ll ans = 0;
	Loop (x,0,a) {
		ll dard = stir[a-x] * C(b-a+x, x) % mod;
		ans += x%2? -dard: dard;
	}
	ans = (ans%mod+mod) % mod;
	cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 7764 KB Output is correct
2 Correct 591 ms 7692 KB Output is correct
3 Correct 583 ms 7580 KB Output is correct
4 Correct 585 ms 7568 KB Output is correct
5 Correct 596 ms 7572 KB Output is correct
6 Correct 583 ms 7756 KB Output is correct
7 Correct 582 ms 7672 KB Output is correct
8 Correct 588 ms 7708 KB Output is correct
9 Correct 587 ms 7692 KB Output is correct
10 Correct 587 ms 7584 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 7764 KB Output is correct
2 Correct 591 ms 7692 KB Output is correct
3 Correct 583 ms 7580 KB Output is correct
4 Correct 585 ms 7568 KB Output is correct
5 Correct 596 ms 7572 KB Output is correct
6 Correct 583 ms 7756 KB Output is correct
7 Correct 582 ms 7672 KB Output is correct
8 Correct 588 ms 7708 KB Output is correct
9 Correct 587 ms 7692 KB Output is correct
10 Correct 587 ms 7584 KB Output is correct
11 Correct 599 ms 7556 KB Output is correct
12 Correct 590 ms 7616 KB Output is correct
13 Correct 591 ms 7740 KB Output is correct
14 Correct 574 ms 7696 KB Output is correct
15 Execution timed out 609 ms 7588 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 7764 KB Output is correct
2 Correct 591 ms 7692 KB Output is correct
3 Correct 583 ms 7580 KB Output is correct
4 Correct 585 ms 7568 KB Output is correct
5 Correct 596 ms 7572 KB Output is correct
6 Correct 583 ms 7756 KB Output is correct
7 Correct 582 ms 7672 KB Output is correct
8 Correct 588 ms 7708 KB Output is correct
9 Correct 587 ms 7692 KB Output is correct
10 Correct 587 ms 7584 KB Output is correct
11 Correct 599 ms 7556 KB Output is correct
12 Correct 590 ms 7616 KB Output is correct
13 Correct 591 ms 7740 KB Output is correct
14 Correct 574 ms 7696 KB Output is correct
15 Execution timed out 609 ms 7588 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 7764 KB Output is correct
2 Correct 591 ms 7692 KB Output is correct
3 Correct 583 ms 7580 KB Output is correct
4 Correct 585 ms 7568 KB Output is correct
5 Correct 596 ms 7572 KB Output is correct
6 Correct 583 ms 7756 KB Output is correct
7 Correct 582 ms 7672 KB Output is correct
8 Correct 588 ms 7708 KB Output is correct
9 Correct 587 ms 7692 KB Output is correct
10 Correct 587 ms 7584 KB Output is correct
11 Correct 599 ms 7556 KB Output is correct
12 Correct 590 ms 7616 KB Output is correct
13 Correct 591 ms 7740 KB Output is correct
14 Correct 574 ms 7696 KB Output is correct
15 Execution timed out 609 ms 7588 KB Time limit exceeded
16 Halted 0 ms 0 KB -