QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226212#5406. 随机游走chenxinyang200670 30ms15688kbC++143.8kb2023-10-25 18:26:212023-10-25 18:26:22

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 18:26:22]
  • 评测
  • 测评结果:70
  • 用时:30ms
  • 内存:15688kb
  • [2023-10-25 18:26:21]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
Z fact[1000005],ifac[1000005],inv[1000005];

Z C(int N,int M){
    if(N < M || M < 0) return 0;
    return fact[N] * ifac[M] * ifac[N - M];
}

void init(int L){
    fact[0] = 1;
    rep(i,1,L) fact[i] = fact[i - 1] * i;
    ifac[L] = 1 / fact[L];
    per(i,L - 1,0) ifac[i] = ifac[i + 1] * (i + 1);
    rep(i,1,L) inv[i] = ifac[i] * fact[i - 1];
}
int n;

int main(){
    scanf("%d",&n);
    init(2 * n);
    Z ans = 0,temp;
    rep(i,0,n){
        temp = C(2 * n,i) * power(n - i,2 * n + 1);
        if(i % 2) ans -= temp;
        else ans += temp;
    }
    ans /= 2 * n + 1;
    ans /= fact[2 * n];
    ans *= 2;
    printf("%d\n",ans.val());
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 3ms
memory: 15548kb

input:

1

output:

333333336

result:

ok 1 number(s): "333333336"

Test #2:

score: 0
Accepted
time: 0ms
memory: 15500kb

input:

2

output:

266666669

result:

ok 1 number(s): "266666669"

Test #3:

score: 0
Accepted
time: 0ms
memory: 15648kb

input:

3

output:

769047625

result:

ok 1 number(s): "769047625"

Subtask #2:

score: 10
Accepted

Test #4:

score: 10
Accepted
time: 0ms
memory: 15632kb

input:

4

output:

877865968

result:

ok 1 number(s): "877865968"

Test #5:

score: 0
Accepted
time: 2ms
memory: 15564kb

input:

5

output:

733342859

result:

ok 1 number(s): "733342859"

Test #6:

score: 0
Accepted
time: 2ms
memory: 15584kb

input:

6

output:

655899114

result:

ok 1 number(s): "655899114"

Test #7:

score: 0
Accepted
time: 3ms
memory: 15644kb

input:

7

output:

946326757

result:

ok 1 number(s): "946326757"

Test #8:

score: 0
Accepted
time: 0ms
memory: 15648kb

input:

8

output:

230714822

result:

ok 1 number(s): "230714822"

Test #9:

score: 0
Accepted
time: 3ms
memory: 15632kb

input:

9

output:

782967541

result:

ok 1 number(s): "782967541"

Test #10:

score: 0
Accepted
time: 0ms
memory: 15556kb

input:

10

output:

732371611

result:

ok 1 number(s): "732371611"

Subtask #3:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 2ms
memory: 15684kb

input:

15

output:

677123472

result:

ok 1 number(s): "677123472"

Test #12:

score: 0
Accepted
time: 0ms
memory: 15644kb

input:

13

output:

168974634

result:

ok 1 number(s): "168974634"

Test #13:

score: 0
Accepted
time: 2ms
memory: 15548kb

input:

26

output:

213343876

result:

ok 1 number(s): "213343876"

Test #14:

score: 0
Accepted
time: 2ms
memory: 15684kb

input:

29

output:

631124616

result:

ok 1 number(s): "631124616"

Subtask #4:

score: 15
Accepted

Test #15:

score: 15
Accepted
time: 2ms
memory: 15644kb

input:

37

output:

349256161

result:

ok 1 number(s): "349256161"

Test #16:

score: 0
Accepted
time: 2ms
memory: 15648kb

input:

104

output:

351095881

result:

ok 1 number(s): "351095881"

Test #17:

score: 0
Accepted
time: 0ms
memory: 15500kb

input:

194

output:

895504391

result:

ok 1 number(s): "895504391"

Test #18:

score: 0
Accepted
time: 3ms
memory: 15564kb

input:

197

output:

923555376

result:

ok 1 number(s): "923555376"

Test #19:

score: 0
Accepted
time: 0ms
memory: 15620kb

input:

198

output:

512220517

result:

ok 1 number(s): "512220517"

Subtask #5:

score: 15
Accepted

Test #20:

score: 15
Accepted
time: 3ms
memory: 15560kb

input:

562

output:

255062346

result:

ok 1 number(s): "255062346"

Test #21:

score: 0
Accepted
time: 0ms
memory: 15584kb

input:

1007

output:

735041605

result:

ok 1 number(s): "735041605"

Test #22:

score: 0
Accepted
time: 2ms
memory: 15628kb

input:

1788

output:

208261384

result:

ok 1 number(s): "208261384"

Test #23:

score: 0
Accepted
time: 0ms
memory: 15644kb

input:

1980

output:

875427987

result:

ok 1 number(s): "875427987"

Test #24:

score: 0
Accepted
time: 0ms
memory: 15560kb

input:

1983

output:

571776252

result:

ok 1 number(s): "571776252"

Test #25:

score: 0
Accepted
time: 0ms
memory: 15504kb

input:

1992

output:

12983695

result:

ok 1 number(s): "12983695"

Subtask #6:

score: 15
Accepted

Test #26:

score: 15
Accepted
time: 2ms
memory: 15676kb

input:

3946

output:

977435333

result:

ok 1 number(s): "977435333"

Test #27:

score: 0
Accepted
time: 4ms
memory: 15640kb

input:

65944

output:

312666196

result:

ok 1 number(s): "312666196"

Test #28:

score: 0
Accepted
time: 17ms
memory: 15624kb

input:

163815

output:

163767254

result:

ok 1 number(s): "163767254"

Test #29:

score: 0
Accepted
time: 15ms
memory: 15636kb

input:

198732

output:

911833524

result:

ok 1 number(s): "911833524"

Test #30:

score: 0
Accepted
time: 19ms
memory: 15632kb

input:

199287

output:

910277128

result:

ok 1 number(s): "910277128"

Test #31:

score: 0
Accepted
time: 15ms
memory: 15636kb

input:

199819

output:

561747634

result:

ok 1 number(s): "561747634"

Subtask #7:

score: 0
Runtime Error

Test #32:

score: 30
Accepted
time: 30ms
memory: 15688kb

input:

315618

output:

602805814

result:

ok 1 number(s): "602805814"

Test #33:

score: -30
Runtime Error

input:

1130465

output:


result: