Submission #2627937


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int N, M, dp[309][309], p[309][309], invp[309][309], c[309][309];
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 main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
{
    p[i][0] = 1;
    for (int j=1; j<=M + 1; j++)
        p[i][j] = mul (p[i][j - 1], i);
    invp[i][0] = 1;
    int aux = power (i, mod - 2);
    for (int j=1; j<=M + 1; j++)
        invp[i][j] = mul (invp[i][j - 1], aux);
}
c[0][0] = 1;
for (int i=1; i<=N; i++)
    for (int j=0; j<=i; j++)
        c[i][j] = add (c[i - 1][j], (j == 0 ? 0 : c[i - 1][j - 1]));
for (int i=0; i<=M; i++)
    dp[1][i] = 1;
for (int i=2; i<=N; i++)
{
    for (int j=1; j<=M; j++)
        dp[i][j] = p[i][j + 1];
    for (int k=1; k<i; k++)
    {
        int curr = 0;
        for (int l=0; l<=M; l++)
        {
            adto (curr, mul (mul (c[i][k], dp[k][l]), invp[i - k][l]));
            if (l > 0)
                dp[i][l] = subtract (dp[i][l], mul (curr, p[i - k][l]));
        }
    }
}
printf ("%d\n", mul (dp[N][M], power (N, mod - 2)));
return 0;
}

Submission Info

Submission Time
Task F - Road of the King
User geniucos
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1624 Byte
Status AC
Exec Time 176 ms
Memory 1664 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
                        ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 16
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 3 ms 1664 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 19 ms 640 KB
01-07.txt AC 165 ms 1664 KB
01-08.txt AC 174 ms 1664 KB
01-09.txt AC 175 ms 1664 KB
01-10.txt AC 176 ms 1664 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 50 ms 1024 KB
sample-03.txt AC 76 ms 1664 KB