제출 #344907

#제출 시각아이디문제언어결과실행 시간메모리
344907limabeansZapina (COCI20_zapina)C++17
110 / 110
510 ms8556 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...