Submission #217187

#	Time	Username	Problem	Language	Result	Execution time	Memory
217187		combi1k1	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	464 ms	3576 KiB

ruins3

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 1500;
const int   mod = 1e9 + 7;

void add(int &a,int b)  {
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub(int &a,int b)  {
    a -= b;
    if (a <  0)
        a += mod;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}
int Pow(int a,int b)    {
    int ans = 1;
    while (b)   {
        if(b & 1)   ans = mul(ans,a);
        a = mul(a,a);   b >>= 1;
    }
    return  ans;
}
int inv(int a,int p)    {
    return  a == 1 ? 1 : p - 1ll * p * inv(p % a,a) / a;
}

typedef pair<int,int>   ii;

int Fac[N];
int Inv[N];

int Ckn(int n,int k)    {
    if (n < k)  return  0;
    if (k < 0)  return  0;

    return  mul(Fac[n],mul(Inv[k],Inv[n - k]));
}
int a[N];
int f[N][N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Fac[0] = Inv[0] = 1;

    for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i);     Inv[N - 1] = inv(Fac[N - 1],mod);
    for(int i = N - 2 ; i ; --i)    Inv[i] = mul(Inv[i + 1],i + 1);

    int n;  cin >> n;

    for(int i = 0 ; i < n ; ++i)    cin >> a[i];

    f[0][0] = 1;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j <= n ; ++j)   if (f[i][j])
        for(int k = 0 ; k <= min(n,a[i] - i - 1) - j ; ++k) {
            int nxt = f[i][j];

            nxt = mul(nxt,Fac[k + k]);
            nxt = mul(nxt,Inv[k]);

            nxt = mul(nxt,Ckn(a[i] - i - j - 1,k));

            if(!k)  nxt = mul(nxt,j - i);

            add(f[i + 1][j + k],nxt);
        }

    int ans = f[n][n];

    for(int i = 0 ; i < n ; ++i)
        ans = mul(ans,500000004);

    cout << ans << endl;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:63:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i);     Inv[N - 1] = inv(Fac[N - 1],mod);
     ^~~
ruins3.cpp:63:69: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i);     Inv[N - 1] = inv(Fac[N - 1],mod);
                                                                     ^~~

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42