oj.uz

Submission #712814

# Submission time Handle Problem Language Result Execution time Memory
712814 2023-03-20T07:54:38 Z ymm Asceticism (JOI18_asceticism) C++17
24 / 100
 600 ms 5580 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 = 131072;
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) >= mod? (x) - mod: x)
#define SMOD(x) ((x) = MOD(x))

template<int n>
void karatsuba(int *__restrict__ a, int *__restrict__ b, int *__restrict__ ans, int *__restrict__ tmp)
{
	if constexpr (n == 16) {
		static ull ansl[32];
		Loop (i,0,2*n-1)
			ansl[i] = 0;
		Loop (i,0,n) Loop (j,0,n)
			ansl[i+j] += (ull)a[i] * b[j];
		Loop (i,0,2*n-1)
			ans[i] = ansl[i] % mod;
		ans[2*n-1] = 0;
		return;
	}
	Loop (i,0,n) {
		tmp[i] = a[i];
		tmp[i+n] = b[i];
	}
	Loop (i,0,n/2)
		a[i+n/2] = b[i];
	karatsuba<n/2>(a, a+n/2, ans, b);
	Loop (i,0,n/2) {
		a[i] = tmp[i+n/2];
		a[i+n/2] = tmp[i+n+n/2];
	}
	karatsuba<n/2>(a, a+n/2, ans+n, b);
	Loop (i,0,n/2) {
		a[i] = MOD(tmp[i] + tmp[i+n/2]);
		a[i+n/2] = MOD(tmp[i+n] + tmp[i+n+n/2]);
	}
	karatsuba<n/2>(a, a+n/2, b, tmp);
	Loop (i,0,n)
		b[i] = MOD(MOD(b[i] + mod - ans[i]) + mod - ans[i+n]);
	Loop (i,0,n)
		ans[i+n/2] = MOD(ans[i+n/2] + b[i]);
}

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.resize(2*N);
	vector<int> tmp(2*N);
	karatsuba<N>(&A[0], &B[0], &stir[0], &tmp[0]);
	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';
}

Compilation message

asceticism.cpp: In instantiation of 'void karatsuba(int*, int*, int*, int*) [with int n = 1]':
asceticism.cpp:70:16:   recursively required from 'void karatsuba(int*, int*, int*, int*) [with int n = 65536]'
asceticism.cpp:70:16:   required from 'void karatsuba(int*, int*, int*, int*) [with int n = 131072]'
asceticism.cpp:98:46:   required from here
asceticism.cpp:70:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   70 |  karatsuba<n/2>(a, a+n/2, ans, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
asceticism.cpp:75:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   75 |  karatsuba<n/2>(a, a+n/2, ans+n, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
asceticism.cpp:80:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   80 |  karatsuba<n/2>(a, a+n/2, b, tmp);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
asceticism.cpp: In instantiation of 'void karatsuba(int*, int*, int*, int*) [with int n = 0]':
asceticism.cpp:70:16:   recursively required from 'void karatsuba(int*, int*, int*, int*) [with int n = 65536]'
asceticism.cpp:70:16:   required from 'void karatsuba(int*, int*, int*, int*) [with int n = 131072]'
asceticism.cpp:98:46:   required from here
asceticism.cpp:70:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   70 |  karatsuba<n/2>(a, a+n/2, ans, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
asceticism.cpp:75:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   75 |  karatsuba<n/2>(a, a+n/2, ans+n, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
asceticism.cpp:80:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   80 |  karatsuba<n/2>(a, a+n/2, b, tmp);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 5460 KB Output is correct
2 Correct 581 ms 5580 KB Output is correct
3 Correct 552 ms 5580 KB Output is correct
4 Correct 550 ms 5460 KB Output is correct
5 Correct 580 ms 5460 KB Output is correct
6 Correct 560 ms 5460 KB Output is correct
7 Correct 557 ms 5580 KB Output is correct
8 Correct 573 ms 5460 KB Output is correct
9 Correct 550 ms 5460 KB Output is correct
10 Correct 554 ms 5460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 5460 KB Output is correct
2 Correct 581 ms 5580 KB Output is correct
3 Correct 552 ms 5580 KB Output is correct
4 Correct 550 ms 5460 KB Output is correct
5 Correct 580 ms 5460 KB Output is correct
6 Correct 560 ms 5460 KB Output is correct
7 Correct 557 ms 5580 KB Output is correct
8 Correct 573 ms 5460 KB Output is correct
9 Correct 550 ms 5460 KB Output is correct
10 Correct 554 ms 5460 KB Output is correct
11 Correct 554 ms 5460 KB Output is correct
12 Correct 564 ms 5580 KB Output is correct
13 Correct 565 ms 5580 KB Output is correct
14 Correct 560 ms 5460 KB Output is correct
15 Correct 555 ms 5460 KB Output is correct
16 Correct 566 ms 5460 KB Output is correct
17 Correct 555 ms 5460 KB Output is correct
18 Correct 571 ms 5460 KB Output is correct
19 Correct 578 ms 5460 KB Output is correct
20 Correct 553 ms 5460 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 5460 KB Output is correct
2 Correct 581 ms 5580 KB Output is correct
3 Correct 552 ms 5580 KB Output is correct
4 Correct 550 ms 5460 KB Output is correct
5 Correct 580 ms 5460 KB Output is correct
6 Correct 560 ms 5460 KB Output is correct
7 Correct 557 ms 5580 KB Output is correct
8 Correct 573 ms 5460 KB Output is correct
9 Correct 550 ms 5460 KB Output is correct
10 Correct 554 ms 5460 KB Output is correct
11 Correct 554 ms 5460 KB Output is correct
12 Correct 564 ms 5580 KB Output is correct
13 Correct 565 ms 5580 KB Output is correct
14 Correct 560 ms 5460 KB Output is correct
15 Correct 555 ms 5460 KB Output is correct
16 Correct 566 ms 5460 KB Output is correct
17 Correct 555 ms 5460 KB Output is correct
18 Correct 571 ms 5460 KB Output is correct
19 Correct 578 ms 5460 KB Output is correct
20 Correct 553 ms 5460 KB Output is correct
21 Execution timed out 603 ms 5472 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 5460 KB Output is correct
2 Correct 581 ms 5580 KB Output is correct
3 Correct 552 ms 5580 KB Output is correct
4 Correct 550 ms 5460 KB Output is correct
5 Correct 580 ms 5460 KB Output is correct
6 Correct 560 ms 5460 KB Output is correct
7 Correct 557 ms 5580 KB Output is correct
8 Correct 573 ms 5460 KB Output is correct
9 Correct 550 ms 5460 KB Output is correct
10 Correct 554 ms 5460 KB Output is correct
11 Correct 554 ms 5460 KB Output is correct
12 Correct 564 ms 5580 KB Output is correct
13 Correct 565 ms 5580 KB Output is correct
14 Correct 560 ms 5460 KB Output is correct
15 Correct 555 ms 5460 KB Output is correct
16 Correct 566 ms 5460 KB Output is correct
17 Correct 555 ms 5460 KB Output is correct
18 Correct 571 ms 5460 KB Output is correct
19 Correct 578 ms 5460 KB Output is correct
20 Correct 553 ms 5460 KB Output is correct
21 Execution timed out 603 ms 5472 KB Time limit exceeded
22 Halted 0 ms 0 KB -