제출 #344907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344907		limabeans	Zapina (COCI20_zapina)	C++17	110 / 110	510 ms	8556 KiB

zapina

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9 + 7;
const int maxn = 355;


int n;
ll dp[maxn][maxn];

const int N = 1010;
ll f[N];
ll C[N][N];


void add(ll &x, ll y) {
    x %= mod;
    y %= mod;
    x += y;
    x %= mod;
}


ll solve(int i, int j, bool flag=false) {
    //cout<<i<<": "<<j<<endl;
    if (i==n) {
	if (flag) {
	    return i!=j;
	}
	return 1;
    }

    if (~dp[i][j]) return dp[i][j];
    ll &res = dp[i][j] = 0;

    // take x tasks
    for (int x=0; x<=j; x++) {
	if (flag) {
	    if (x==i) continue;
	}
	add(res, C[j][x]*solve(i+1,j-x,flag));
    }

    return res;
}



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

    f[0]=1;
    for (int i=1; i<N; i++) {
	f[i]=i*f[i-1]%mod;
    }

    for (int i=0; i<N; i++) {
	C[i][0]=C[i][i]=1;
	for (int j=1; j<i; j++) {
	    C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
    }

    assert(C[4][2]==6);
    

    cin>>n;
    memset(dp,-1,sizeof(dp));
    ll all = solve(1, n);


    memset(dp,-1,sizeof(dp));
    ll none = solve(1,n,true);


    ll res = all - none;
    
    res %= mod;
    res += mod;
    res %= mod;
    cout<<res<<endl;    
    
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55