Submission #993371

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }

const Int MO = 1000000007;
Int dp[302][302][302], pw[303];

// void naive() {
//   int res=0;
//   const int nn=4;
//   for (int a=0;a<nn;++a)for(int b=0;b<nn;++b)for (int c=0;c<nn;++c)for (int d=0;d<nn;++d) for(int e=0;e<nn;++e)
//   for (int f=0;f<nn;++f)for(int g=0;g<nn;++g) {
//     int D[nn][nn];
//     memset(D, 0, sizeof(D));
//     D[0][a] = D[a][b] = D[b][c] = D[c][d] = D[d][e] = D[e][f] = D[f][g]=1;
//     for (int k=0;k<nn;++k)for (int i=0;i<nn; ++i)for(int j=0;j<nn;++j) {
//       D[i][j] |= D[i][k]&&D[k][j];
//     }
//     int ok=1;
//     for (int i=0;i<nn;++i){
//       ok&=D[0][i]&&D[i][0];
//     }
//     if(ok)++res;
//   }
//   printf("NAIVE: %d\n", res);
// }

int main() {
  int N = in();
  int M = in();
  pw[0] = 1;
  for (int i = 1; i <= M; ++i) {
    pw[i] = pw[i - 1] * N % MO;
  }
  dp[0][1][1] = 1;

  Int res = 0;
  for (int i = 0; i < M; ++i) {
    for (int j = 1; j <= i + 1 && j <= N; ++j) {
      for (int k = 1; k <= j; ++k) {
        // 1
        if (j == N) {
          (res += dp[i][j][k] * k % MO * pw[M - i - 1]) %= MO;
          // cerr<<i<<' '<<j<<' '<<k<<' '<<res<<endl;
        } else {
          (dp[i + 1][j][j] += dp[i][j][k] * k) %= MO;
        }

        // already
        (dp[i + 1][j][k] += dp[i][j][k] * (j - k)) %= MO;

        // new
        (dp[i + 1][j + 1][k] += dp[i][j][k] * (N - j)) %= MO;
      }
    }
  }
  // for (int i = 1; i <= M; ++i) {
  //   for (int j = 1; j <= i + 1 && j <= N; ++j) {
  //     printf("%d %d: ", i, j);
  //     for (int k = 1; k <= j; ++k) {
  //       printf("%lld ", dp[i][j][k]);
  //     }
  //     puts("");
  //   }
  // }

  printf("%lld\n", res);

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:34:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘double fin()’:
./Main.cpp:35:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 double fin() { double x; scanf("%lf", &x); return x; }
                                          ^
./Main.cpp: In function ‘Int lin()’:
./Main.cpp:36:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 Int lin() { Int x; scanf("%lld", &x); return x; }
                                     ^

Judge Result