Submission #1149658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149658		dosts	Tents (JOI18_tents)	C++20	48 / 100	2096 ms	14408 KiB

tents

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 3e5+1,MOD = 1e9+7,BL = 1000;

int add(int x,int y){
    return ((x+y >= MOD) ? x+y-MOD : x+y);
}
int mult(int x,int y) {
    return (x*y)%MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x,y/2);
    e = mult(e,e);
    if (y&1) e = mult(e,x);
    return e;
}

int divide(int x,int y) {
    return mult(x,expo(y,MOD-2));
}

int f[N],finv[N];
int pw[3001];
void combo() {
    f[0] = 1;
    pw[0] = 1;
    for (int i=1;i<=3000;i++) pw[i] = mult(pw[i-1],2);
    for (int i=1;i<N;i++) f[i] = mult(i,f[i-1]);
    finv[N-1] = divide(1,f[N-1]);
    for (int i = N-2;i>=0;i--) finv[i] = mult(finv[i+1],i+1);
}

int nck(int n,int k) {
    if (n < k) return 0;
    return mult(f[n],mult(finv[k],finv[n-k]));
}
int emp[3001][3001];
int calc(int n,int m,int y,int v) {
    if (n < y+2*v) return 0;
    if (m < v+2*y) return 0;
    int rowlar = nck(n,y);
    int collar = divide(f[m],mult(f[m-2*y],pw[y]));
    int dikey = nck(m-2*y,v);
    int yatay = divide(f[n-y],mult(f[n-y-2*v],pw[v]));
    int otras = emp[n-y-2*v][m-v-2*y];
    return mult(otras,mult(mult(rowlar,collar),mult(dikey,yatay)));
}
void solve() { 
    combo();
    int n,m;
    cin >> n >> m;
    for (int i=0;i<=n;i++) {
        for (int j = 0;j<=m;j++) {
            int pw = 1;
            for (int t = 0;t <= min(i,j);t++) {
                emp[i][j] = add(emp[i][j],mult(f[t],mult(pw,mult(nck(j,t),nck(i,t)))));
                pw = mult(pw,4);
            }
        }
    }
    int ans = 0;
    for (int i=0;i<=n;i++) {
        for (int j = 0;j<=m;j++) {
            ans = add(ans,calc(n,m,i,j));
        }
    }
    ans = add(ans,MOD-1);
    cout << ans << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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