Submission #1294393

#TimeUsernameProblemLanguageResultExecution timeMemory
1294393thesentro캥거루 (CEOI16_kangaroo)C++20
100 / 100
25 ms23064 KiB
/* _____ _ ____ _ |_ _| |__ ___/ ___| ___ _ __ | |_ _ __ ___ | | | '_ \ / _ \___ \ / _ \ '_ \| __| '__/ _ \ | | | | | | __/___) | __/ | | | |_| | | (_) | |_| |_| |_|\___|____/ \___|_| |_|\__|_| \___/ */ #include <bits/stdc++.h> // #pragma GCC optimize("O3") using namespace std; #define ll long long ll mod = 1e9+7; ll binpow(ll a, ll b) { ll res = 1; while (b>0) { if (b&1) res = (res*a)%mod; a = (a*a)%mod; b>>=1; } return res; } ll gcd(ll x, ll y) { if (y==0) return x; return gcd(y, x%y); } ll dp[2005][2005]; void solve() { ll n,s,f; cin>>n>>s>>f; dp[1][1] = 1; ll fix=0; for (int i=1 ; i<=n ;i++) { if (i==s or i==f) fix++; for (int j=1 ; j<i ; j++) { if (i==s or i==f) { dp[i][j+1] = (dp[i][j+1]+dp[i-1][j])%mod; dp[i][j] = (dp[i][j]+dp[i-1][j])%mod; } else { dp[i][j+1] = (dp[i][j+1]+(j+1-fix)*dp[i-1][j])%mod; dp[i][j-1] = (dp[i][j-1]+(j-1)*dp[i-1][j])%mod; } } } cout<<dp[n][1]<<endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll tt = 1; // cin>>tt; while (tt--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...