Submission #1179412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179412		Valters07	Tents (JOI18_tents)	C++20	100 / 100	137 ms	35788 KiB

tents

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define ld long double
#define en exit(0);
#define pb push_back
#define fi first
#define se second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3005;
const int mod = 1e9+7;
int dp[N][N]; // dp[i][j] - the number of ways to place some number of rooks in a i by j grid, such that no two rooks attack each other
int f[N], invf[N];
int pw2[N], invpw2[N];
int sum(int a, int b)
{
    a+=b;
    if(a>=mod)
        a-=mod;
    if(a<0)
        a+=mod;
    return a;
}
int mul(int a, int b)
{
    return 1ll*a*b%mod;
}
int poww(int n, int k)
{
    int res = 1;
    while(k > 0)
    {
        if(k % 2 == 1)
            res = mul(res,n);
        n = mul(n,n);
        k/=2;
    }
    return res;
}
int C(int n, int k)
{
    return mul(f[n],mul(invf[k],invf[n-k]));
}
int inv(int n)
{
    return poww(n,mod-2);
}
int main()
{
    fio
//    ifstream cin("in.in");
    f[0] = 1;
    for(int i = 1;i < N;i++)
        f[i] = mul(f[i-1],i);
    invf[N-1] = inv(f[N-1]);
    for(int i = N-2;i >= 0;i--)
        invf[i] = mul(invf[i+1],i+1);
    pw2[0] = 1;
    for(int i = 1;i < N;i++)
        pw2[i] = mul(pw2[i-1], 2);
    invpw2[N-1] = inv(pw2[N-1]);
    for(int i = N-2;i>=0;i--)
        invpw2[i] = mul(invpw2[i+1], 2);
    int n, m;
    cin >> n >> m;
    for(int i = 0;i<=n;i++)
        dp[i][0] = 1;
    for(int j = 0;j<=m;j++)
        dp[0][j] = 1;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            dp[i][j] = sum(mul(dp[i-1][j-1], mul(j, 4)), dp[i-1][j]);
    int res = 0;
    for(int hor = 0;hor <= n && 2 * hor <= m;hor++)
    {
        int ways_hor = mul(C(n, hor), mul(C(m, 2 * hor), mul(f[2*hor],invpw2[hor])));
        int hor_left = n - hor, vert_left = m - 2 * hor;
        for(int vert = 0;hor + vert * 2 <= n && 2 * hor + vert <= m;vert++)
        {
            int ways_vert = mul(mul(C(hor_left, vert * 2), mul(f[2*vert],invpw2[vert])), C(vert_left, vert));
            int hor_final = hor_left - vert * 2, vert_final = vert_left - vert;
            int ways_single = dp[hor_final][vert_final];
            res = sum(res, mul(ways_hor, mul(ways_vert, ways_single)));
        }
    }
    res = sum(res, -1);
    cout << res;
    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52