Submission #44948

#	Time	Username	Problem	Language	Result	Execution time	Memory
44948		SpaimaCarpatilor	Asceticism (JOI18_asceticism)	C++17	49 / 100	1083 ms	1532 KiB

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 (stderr)

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 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51