Cod sursa(job #636503)
Utilizator | Heidelbacher Andrei a_h1926 | Data | 19 noiembrie 2011 20:52:54 |
---|---|---|---|
Problema | Dirichlet | Scor | 40 |
Compilator | cpp | Status | done |
Runda | .com 2011 | Marime | 0.6 kb |
#include <cstdio>
#define Mod 9999991
#define NMax 1005
using namespace std;
long long N, S, DP[NMax][NMax];
int main()
{
freopen ("dirichlet.in", "r", stdin);
freopen ("dirichlet.out", "w", stdout);
scanf ("%lld", &N);
DP[0][0]=1;
for (int i=1; i<=N; ++i)
{
DP[i][0]=1;
for (int j=1; j<=i; ++j)
{
if (DP[i-1][j]==0)
{
DP[i-1][j]=DP[i-1][i-1];
}
DP[i][j]=DP[i][j-1]+DP[i-1][j];
DP[i][j]%=Mod;
}
}
printf ("%lld\n", DP[N-1][N]);
return 0;
}