Submission #993340


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int MOD = 1000000007;
const int maxn = 305;

int cnk[maxn][maxn];
int ans[maxn][maxn];
int ans2[maxn][maxn][maxn];
int kk[maxn][maxn];
int pw[maxn][maxn];
int n, m;
int f[maxn];

void add(int &x, ll y)
{
    x = (x + y) % MOD;
}

int main()
{
    scanf("%d%d", &n, &m);
    cnk[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        cnk[i][0] = 1;
        for (int j = 1; j <= i; j++) cnk[i][j] = (cnk[i - 1][j - 1] + cnk[i - 1][j]) % MOD;
    }
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = ((ll)f[i - 1] * i) % MOD;
    for (int i = 1; i <= n; i++)
    {
        pw[i][0] = 1;
        for (int j = 1; j <= m; j++) pw[i][j] = ((ll)pw[i][j - 1] * i) % MOD;
    }
    kk[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= m; j++)
        {
            for (int t = i; t >= i; t--) add(kk[i][j], (((ll)kk[i - 1][t - 1] * pw[i][j - t]) % MOD) * i);
        }
    }
//     cout << f[n - 1] << endl;
//     ans[0][1] = 1;
//     for (int i = 0; i < m; i++)
//     {
//         for (int j = 1; j <= n; j++) if (ans[i][j] != 0)
//         {
// //             cout << i << ' ' << j << ' ' << ans[i][j] << endl;
//             for (int k = 0; k <= n - j && i + k + 1 <= m; k++)
//             {
//                 for (int t = 0; i + k + t + 1 <= m; t++)
//                 {
//                     add(ans[i + k + t + 1][j + k], (((ll)ans[i][j] * kk[k][k + t]) % MOD) * j);
//                 }
//             }
//         }
//     }
//     cout << ans[m][n] << endl;
    ans2[0][1][0] = 1;
    for (int i = 0; i < m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 0; k + j <= n; k++) if (ans2[i][j][k] != 0)
            {
                add(ans2[i + 1][j + k][0], ((ll)ans2[i][j][k] * j));
                add(ans2[i + 1][j][k], ((ll)ans2[i][j][k] * k));
                add(ans2[i + 1][j][k + 1], ((ll)ans2[i][j][k] * (n - j - k)));
            }
        }
    }
    int answer = 0;
    for (int i = 0; i < n; i++) add(answer, ans2[m][n][i]);
    cout << answer << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Road of the King
User KAN
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2486 Byte
Status AC
Exec Time 165 ms
Memory 55936 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:40:26: 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 × 13
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
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 6 ms 1792 KB
01-04.txt AC 4 ms 1024 KB
01-05.txt AC 11 ms 4608 KB
01-06.txt AC 63 ms 28544 KB
01-07.txt AC 162 ms 55552 KB
01-08.txt AC 165 ms 55936 KB
01-09.txt AC 164 ms 55936 KB
01-10.txt AC 164 ms 55936 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 100 ms 41984 KB
sample-03.txt AC 56 ms 15104 KB