답안 #44948 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44948	2018-04-09T19:54:53 Z	SpaimaCarpatilor	Asceticism (JOI18_asceticism)	C++17	49 / 100	600 ms	1532 KB

asceticism

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #44948

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 20.0 / 20.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 51.0

Subtask #1
4.0 / 4.0

Subtask #2
20.0 / 20.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 51.0