Skip to content

Instantly share code, notes, and snippets.

@GoBigorGoHome
Created July 9, 2018 13:21
Show Gist options
  • Save GoBigorGoHome/68219936a27c5b47e75bfa563f56be25 to your computer and use it in GitHub Desktop.
Save GoBigorGoHome/68219936a27c5b47e75bfa563f56be25 to your computer and use it in GitHub Desktop.
CodeChef July 18 E brute-force solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x <<": " << (x) << endl
//在每个函数的入口处执行一次,出口处执行一次。然后就可以快速得知是哪个地方段错误了
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#ifdef LOCAL
#define see(x) cout << #x << ": " << (x) << endl
#endif
#ifndef LOCAL
#define see(x)
#endif
#define RED "\033[31m"
#define RESET "\033[0m"
#define alert(x) cerr << RED << x << RESET << endl
#ifndef LOCAL
#define see(x)
#endif
#define rep(n) for(int _ = 0; _ != (n); ++_)
//#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define Rng(i, n) for(int i = 0; i != (n); ++i)
#define rng(i, a, b) for(int i = (a); i < (b); ++i)
#define RNG(i, a) for(auto &i: (a))
#define dwn(i, r, l) for(int i = (r); i>=(l); i--)
namespace std {
template<class T>
T begin(std::pair<T, T> p)
{
return p.first;
}
template<class T>
T end(std::pair<T, T> p)
{
return p.second;
}
}
#if __cplusplus < 201402L
template<class Iterator>
std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it)
{
return std::reverse_iterator<Iterator>(it);
}
#endif
template<class Range>
std::pair<std::reverse_iterator<decltype(begin(std::declval<Range>()))>, std::reverse_iterator<decltype(begin(std::declval<Range>()))>> make_reverse_range(Range &&r)
{
return std::make_pair(make_reverse_iterator(::begin(r)), make_reverse_iterator(::end(r)));
}
#define RRNG(x, cont) for (auto &x: make_reverse_range(cont))
template<class T> int sign(const T &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; }
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> void Min(T &a, const T &b){ a = min(a, b); }
template<class T> void Max(T &a, const T &b){ a = max(a, b); }
template<typename T> void println(const T &t) { cout << t << '\n'; }
template<typename T, typename ...Args> void println(const T &t, const Args &...rest) { cout << t << ' '; println(rest...); }
template<typename T> void print(const T &t) { cout << t << ' '; }
template<typename T, typename ...Args> void print(const T &t, const Args &...rest) { cout << t; print(rest...); }
// this overload is chosen when there's only one argument
template<class T> void scan(T &t) { cin >> t; }
template<class T, class ...Args> void scan(T &a, Args &...rest) { cin >> a; scan(rest...); }
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using pip = pair<int, pii>;
using szt = size_t;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using pli = pair<ll,int>;
int cas;
const double pi = acos(-1);
ll mod = 1e9 + 7;
template<class T>
inline void add_mod(T &a, const T &b) {
a += b;
if (a >= mod) a -= mod;
}
template<class T>
void sub_mod(T &a, const T &b){
a -= b;
if (a < 0) a += mod;
}
auto bo=[](int x){ //二进制输出
bitset<5> a(x);
cout << a << endl;
};
mat operator*(const mat &a, const mat &b) {
mat c(a.size(), vec(b[0].size()));
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[0].size(); j++) {
if (a[i][j]) { // optimization for sparse matrix
for (int k = 0; k < b[0].size(); k++) {
add_mod(c[i][k], a[i][j] * b[j][k] % mod);
}
}
}
}
return c;
}
vec operator*(const mat &a, const vec &b) {
vec c(a.size());
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[0].size(); j++) {
add_mod(c[i], a[i][j] * b[j] % mod);
}
}
return c;
}
mat pow(mat a, ull n) {
mat res(a.size(), vec(a[0].size()));
for (int i = 0; i < a.size(); i++) {
res[i][i] = 1;
}
while (n) {
if (n & 1) {
res = res * a;
}
a = a * a;
n >>= 1;
}
return res;
}
std::ostream& operator<<(std::ostream& os, __int128 T) {
if (T<0) os<<"-";
if (T>=10 ) os<<T/10;
if (T<=-10) os<<(-(T/10));
return os<<( (int) (T%10) >0 ? (int) (T%10) : -(int) (T%10) ) ;
}
__int128 LPOW(__int128 x, ll n) {
__int128 res = 1;
for (; n; n /= 2, x *= x, x %= mod) {
if (n & 1) {
res *= x;
res %= mod;
}
}
return res;
}
ll POW(ll x, ll n){
ll res = 1;
for (; n; n /= 2, x *= x, x %= mod) {
if (n & 1) {
res *= x;
res %= mod;
}
}
return res;
}
ll INV(ll x) {
return POW(x, mod - 2);
}
ll inv(ll x){
// see(x);
return x == 1? 1: (mod - mod/x * inv(mod%x) % mod);
}
// 2D rotation
void rotate(double &x, double &y, double theta) {
double tx = cos(theta) * x - sin(theta) * y;
double ty = sin(theta) * x + cos(theta) * y;
x = tx, y = ty;
}
namespace bit {
const int BIT_N = 1e5 + 5;
int bit[BIT_N];
int sum(int x) {
int res = 0;
while (x) {
res += bit[x];
x -= x & -x;
}
return res;
}
int sum(int l, int r) {
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
void add(int x, int v, int n) {
while (x <= n) {
bit[x] += v;
x += x & -x;
}
}
}
namespace util{
int len(ll x){return snprintf(nullptr, 0, "%lld", x);}
vi get_d(ll x){
vi res;
while(x) {
res.pb(x%10);
x /= 10;
}
reverse(all(res));
return res;
}
template <class T> T parity(const T &a){
return a & 1;
}
template <class T>
void out (const vector<T> &a){
std::copy(a.begin(), a.end(), std::ostream_iterator<T>(std::cout, ", "));
cout << endl;
};
}
using namespace util;
// #include <ext/pb_ds/priority_queue.hpp>
// typedef __gnu_pbds :: priority_queue<pip, less<pip>, __gnu_pbds::thin_heap_tag > Heap;
// Heap h;
// Heap::point_iterator pos[N][N];
const ll LINF = LLONG_MAX/10;
const int INF = INT_MAX/10;
const int M = 3000 + 5;
const int N = 3e5+5;
int main() {
// Single Cut of Failure taught me
cout << std::fixed; // 使所有实数(默认)输出6位小数,即使实际小数位数多于6位。
cout << setprecision(10);
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("main.in", "r", stdin);
// freopen("main.out", "w", stdout);
#endif
vl inv(3e5+5);
vl fact(3e5+5);
fact[0] = 1;
rng(i, 1, fact.size()) fact[i] = (i * fact[i-1]) % mod;
inv[1] = 1;
rng(i, 2, inv.size()) {
inv[i] = mod - mod/i*inv[mod%i] % mod;
}
int T = 1;
// scan(T);
while(T--) {
int n;
scan(n);
// see(n);
if(n <= 2) println(0);
else{
using poly = vl; // 多项式
auto eval = [](const poly & a, ll x){
ll res = 0;
dwn(i, a.size()-1, 0) {
res *= x;
res %= mod;
add_mod(res, a[i]); // 保证 0<=res<mod, 0<=a[i]<= mod
}
return res;
};
auto integral = [&inv, &eval](poly &a){
a.pb(0);
dwn(i, a.size()-2, 0){
a[i+1] = a[i] * inv[i+1] % mod;
}
a[0] = 0;
add_mod(a[0], mod - eval(a, inv[2]));
};
poly a = {1, mod-1};
rng(i, 3, n+1) {
integral(a); // 积分之后,a是i-1次多项式
ll t1 = mod - inv[2], t2 = mod - 2;
ll fm = ::inv(fact[i-1]);
ll comb = POW(t1, i-1) * fm % mod; // (-1/2)^{n-1} 除以分母 (i-1)!
rng(j, 0, i){
add_mod(a[j], mod - comb);
// comb(i-1, j) x^j
// comb(i-1, j+1) = comb(i-1, j) * (i - 1 - j) / (j + 1);
comb *= (i - 1 - j) * inv[j+1] % mod * t2 % mod;
comb %= mod;
}
add_mod(a[0], POW(inv[2], i - 1) * fm % mod);
}
ll ans = 0;
RNG(x, a){
add_mod(ans, x);
}
if(ans < 0) ans += mod;
println(ans * fact[n-1] % mod);
}
}
#ifdef LOCAL
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment