oj.uz

Submission #44948

# Submission time Handle Problem Language Result Execution time Memory
44948 2018-04-09T19:54:53 Z SpaimaCarpatilor Asceticism (JOI18_asceticism) C++17
49 / 100
 600 ms 1532 KB 
#include<bits/stdc++.h>

using namespace std;

int N, K, dp[3009][3009], v0[3009], ways[3009];
const int mod = 1e9 + 7;

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int subtract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}
void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

int power (int a, int b)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = mul (p, a);
        a = mul (a, a);
    }
    return p;
}

int fac[200009], inv[200009];
void Prec (int lim){fac[0] = inv[0] = 1;for (int i=1; i<=lim; i++)fac[i] = mul (fac[i - 1], i);
inv[lim] = power (fac[lim], mod - 2);for (int i=lim - 1; i>=0; i--)inv[i] = mul (inv[i + 1], i + 1);}
int comb (int N, int K){int ans = mul (fac[N], inv[N - K]);ans = mul (ans, inv[K]);return ans;}

int coef[109][109];
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &K), K --, Prec (N + 1);

/*for (int i=1; i<=N; i++)
    coef[i][i] = 1;
for (int i=N; i>=1; i--)
    for (int j=i + 1; j<=N; j++)
        for (int k=1; k<=N; k++)
            coef[i][k] = subtract (coef[i][k], mul (coef[j][k], comb (j, i)));

for (int i=1; i<=N; i++, printf ("\n"))
    for (int j=1; j<=N; j++)
        if (coef[i][j] >= mod - 100000) printf ("%3d ", coef[i][j] - mod);
        else printf ("%3d ", coef[i][j]);
printf ("\n");*/

dp[0][0] = 1;
/*for (int i=0; i<N; i++)
    for (int j=0; j<=N; j++)
        for (int k=1; j + k<=N; k++)
            adto (dp[i + 1][j + k], mul (dp[i][j], inv[k]));
for (int i=0; i<=N; i++)
    v0[i] = mul (fac[N], dp[N - i][N]);
that would be K! * stirling
*/
for (int i=1; i<=N; i++)
{
    ways[i] = power (i, N);
    for (int j=1; j<i; j++)
        ways[i] = subtract (ways[i], mul (ways[j], comb (i, j)));
}
for (int i=0; i<=N; i++)
    v0[i] = ways[N - i];
/*for (int i=1; i<=N; i++)
    printf ("%d ", v0[i]);
printf ("\n");*/
int ans = 0;
for (int K2=K; K2<=N; K2++)
{
    int curr = mul (v0[K2], comb (K2, K));
    if (K2 % 2 == K % 2) adto (ans, curr);
    else ans = subtract (ans, curr);
}
printf ("%d\n", ans);
return 0;
}

Compilation message

asceticism.cpp: In function 'int main()':
asceticism.cpp:35:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &K), K --, Prec (N + 1);
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 2 ms 660 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 2 ms 660 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 748 KB Output is correct
20 Correct 2 ms 748 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 2 ms 660 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 748 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 6 ms 748 KB Output is correct
22 Correct 6 ms 748 KB Output is correct
23 Correct 6 ms 748 KB Output is correct
24 Correct 6 ms 748 KB Output is correct
25 Correct 9 ms 748 KB Output is correct
26 Correct 8 ms 748 KB Output is correct
27 Correct 7 ms 748 KB Output is correct
28 Correct 3 ms 748 KB Output is correct
29 Correct 2 ms 748 KB Output is correct
30 Correct 7 ms 748 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 2 ms 660 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 748 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 6 ms 748 KB Output is correct
22 Correct 6 ms 748 KB Output is correct
23 Correct 6 ms 748 KB Output is correct
24 Correct 6 ms 748 KB Output is correct
25 Correct 9 ms 748 KB Output is correct
26 Correct 8 ms 748 KB Output is correct
27 Correct 7 ms 748 KB Output is correct
28 Correct 3 ms 748 KB Output is correct
29 Correct 2 ms 748 KB Output is correct
30 Correct 7 ms 748 KB Output is correct
31 Execution timed out 1083 ms 1532 KB Time limit exceeded
32 Halted 0 ms 0 KB -