作者：碎月
链接：https://zhuanlan.zhihu.com/p/629838090
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int mod = 1e9 + 7;
const int N = 210;

int fac[N], invfac[N];
int f[N], g[N];
int n, k;
i64 t;

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}	
	return res;
}

int inv(int x) {
	return qpow(x, mod - 2);
}

void init_fac(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = 1ll * fac[i - 1] * i % mod;
	}
	invfac[n] = inv(fac[n]);
	for (int i = n - 1; ~i; i--) {
		invfac[i] = 1ll * invfac[i + 1] * (i + 1) % mod;
	}
}

int binom(int a, int b) {
	if (a < b) return 0;
	return 1ll * fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}

struct Matrix {
	int v[N][N];	
	Matrix (int t = 0) {
		memset(v, 0, sizeof v);
		for (int i = 0; i <= n; i++) {
			v[i][i] = t;
		} 
	}
	
	Matrix operator* (Matrix& b) {
		Matrix c;
		for (int i = 0; i <= n; i++)
                        for (int j = 0; j <= n; j++)
                                for (int k = 0; k <= n; k++)
                                        c.v[i][j] = (c.v[i][j] + 1ll * v[i][k] * b.v[k][j] % mod) % mod;
		return c;
	}
	
	Matrix operator^ (i64 b) {
		Matrix res = 1, a = *this;
		while (b) {
			if (b & 1) res = res * a;
			a = a * a;
			b >>= 1;
		}
		return res;
	}
};

int main() {
	cin >> n >> t >> k;
	Matrix B;
	B.v[0][0] = B.v[n][n] = 1;
	for (int i = 1; i < n; i++) {
		B.v[i][i] = 1ll * (i * i + (n - i) * (n - i)) * inv(n * n) % mod;
		B.v[i][i - 1] = B.v[i][i + 1] = 1ll * (n * i - i * i) * inv(n * n) % mod;
	}
	B = B ^ t;	
	for (int i = 0; i <= n; i++) {
		g[i] = B.v[i][0];
	}
	init_fac(n);
	for (int i = n; ~i; i--) {
	        f[i] = g[i];
		for (int j = i + 1; j <= n; j++) {
			f[i] -= 1ll * binom(n - i, j - i) * f[j] % mod;
			f[i] = (f[i] + mod) % mod;
		}	    
	}
	int res = 0;
	for (int i = 0; i <= n - k; i++) {
		res += 1ll * binom(n, i) * f[i] % mod;
		res %= mod;
	}
	cout << res << '\n';
	return 0;    
}

answer.code:4:1: error: extended character 。 is not valid in an identifier
    4 | 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
      | ^
answer.code:4:1: error: extended character 。 is not valid in an identifier
answer.code:1:1: error: ‘作者：碎月’ does not name a type
    1 | 作者：碎月
      | ^~~~~~~~~~
In file included from /usr/include/c++/13/iosfwd:42,
                 from /usr/include/c++/13/ios:40,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:6:
/usr/include/c++/13/bits/postypes.h:68:11: error: ‘ptrdiff_t’ does not name a type
   68 |   typedef ptrdiff_t     streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/13/bits/postypes.h:41:1: note: ‘ptrdiff_t’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/13/bits/exception_ptr.h:38,
                 from /usr/include/c++/13/exception:164,
                 from /usr/include/c++/13/ios:41:
/usr/include/c++/13/new:126:26: error: declaration of ‘operator new’ as non-function
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/13/new:126:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/13/cwchar:44,
                 from /usr/include/c++/13/bits/postypes.h:40:
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  127 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/13/new:128:26: error: declaration of ‘operator new []’ as non-function
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/13/new:128:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  129 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/13/new:135:34: error: ‘std::size_t’ has not been declared
  135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                  ^~~~~~
/usr/include/c++/13/new:137:36: error: ‘std::size_t’ has not been declared
  137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                    ^~~~~~
/usr/include/c++/13/new:140:26: error: declaration of ‘operator new’ as non-function
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/13/new:140:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:140:52: error: expected primary-expression before ‘const’
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/13/new:142:26: error: declaration of ‘operator new []’ as non-function
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/13/new:142:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:142:54: error: expected primary-expression before ‘const’
  142 | _GLIBCXX_NODISC...