oj.uz

Submission #712822

# Submission time Handle Problem Language Result Execution time Memory
712822 2023-03-20T08:04:36 Z ymm Asceticism (JOI18_asceticism) C++17
0 / 100
 600 ms 5460 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)

template<int n>
void karatsuba(int *__restrict__ a, int *__restrict__ b, int *__restrict__ ans, int *__restrict__ tmp)
{
	if constexpr (n == 8) {
		static ull ansl[2*n];
		Loop (i,0,2*n)
			ansl[i] = 0;
		Loop (i,0,n) Loop (j,0,n)
			ansl[i+j] += (ull)a[i] * b[j];
		Loop (i,0,2*n)
			ans[i] = ansl[i] % mod;
		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:68:16:   recursively required from 'void karatsuba(int*, int*, int*, int*) [with int n = 65536]'
asceticism.cpp:68:16:   required from 'void karatsuba(int*, int*, int*, int*) [with int n = 131072]'
asceticism.cpp:96:46:   required from here
asceticism.cpp:68:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   68 |  karatsuba<n/2>(a, a+n/2, ans, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
asceticism.cpp:73:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   73 |  karatsuba<n/2>(a, a+n/2, ans+n, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
asceticism.cpp:78:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   78 |  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:68:16:   recursively required from 'void karatsuba(int*, int*, int*, int*) [with int n = 65536]'
asceticism.cpp:68:16:   required from 'void karatsuba(int*, int*, int*, int*) [with int n = 131072]'
asceticism.cpp:96:46:   required from here
asceticism.cpp:68:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   68 |  karatsuba<n/2>(a, a+n/2, ans, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
asceticism.cpp:73:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   73 |  karatsuba<n/2>(a, a+n/2, ans+n, b);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
asceticism.cpp:78:16: warning: passing argument 1 to 'restrict'-qualified parameter aliases with argument 2 [-Wrestrict]
   78 |  karatsuba<n/2>(a, a+n/2, b, tmp);
      |  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 649 ms 5460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 649 ms 5460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 649 ms 5460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 649 ms 5460 KB Time limit exceeded
2 Halted 0 ms 0 KB -