Submission #19002

#TimeUsernameProblemLanguageResultExecution timeMemory
19002kriii비트 (kriii4_Q)C++14
100 / 100
205 ms1912 KiB
#include <stdio.h> #include <vector> using namespace std; const long long mod = 1000000007; void add(long long &a, long long b) { a = (a + b) % mod; } void mult(long long &a, long long b) { a = (a * b) % mod; } long long fpow(long long a, long long p) { a %= mod; p = (p % (mod - 1) + mod - 1) % (mod - 1); long long r = 1; while (p){ if (p & 1) mult(r,a); mult(a,a); p /= 2; } return r; } vector<long long> gauss(vector<vector<long long> > A) { int n = A.size(); for (int i=0;i<n;i++){ bool good = 0; for (int j=i;j<n;j++) if (A[j][i]){ swap(A[i],A[j]); good = 1; break; } if (!good){fprintf (stderr,"nope");} long long u = fpow(A[i][i],-1); for (int j=i;j<=n;j++) mult(A[i][j],u); for (int k=0;k<n;k++) if (k != i && A[k][i]){ u = A[k][i]; for (int j=i;j<=n;j++) add(A[k][j],mod-A[i][j]*u%mod); } } vector<long long> ret; for (int i=0;i<n;i++) ret.push_back(A[i][n]); return ret; } struct matrix{ matrix(){ n = 0; } matrix(int n_){ n = n_; for (int i=0;i<n;i++) for (int j=0;j<n;j++) A[i][j] = 0; } int n; long long A[101][101]; matrix operator *(matrix t){ matrix r(n); for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) r.A[i][j] = (r.A[i][j] + A[i][k] * t.A[k][j]) % mod; return r; } }; long long prv[101],nxt[101]; long long comb[101][101]; int main() { int N,K; scanf ("%d %d",&N,&K); matrix r(N+1); for (int i=0;i<=N;i++){ if (i > 0) r.A[i][i-1] = i; if (i < N) r.A[i][i+1] = N - i; } long long all = fpow(N,K); prv[0] = 1; while (K){ if (K & 1){ for (int i=0;i<=N;i++) nxt[i] = 0; for (int i=0;i<=N;i++) for (int j=0;j<=N;j++) nxt[i] = (nxt[i] + r.A[i][j] * prv[j]) % mod; for (int i=0;i<=N;i++) prv[i] = nxt[i]; } r = r * r; K /= 2; } vector<vector<long long> > A = vector<vector<long long> >(N+1,vector<long long>(N+2,0)); for (int i=0;i<A.size();i++) A[i][i] = A[i][N+1] = all; A[0][N+1] = 0; for (int i=0;i<=N;i++){ comb[i][0] = comb[i][i] = 1; for (int j=1;j<i;j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod; } for (int i=1;i<=N;i++){ for (int j=1;j<=N;j+=2){ for (int k=0;k<=i&&k<=j;k++){ if (N-i >= j-k){ long long coeff = comb[i][k] * comb[N-i][j-k] % mod; add(A[i][i-k+j-k],mod-coeff*prv[j]%mod); } } } } vector<long long> res = gauss(A); for (int i=1;i<=N;i++) printf ("%lld\n",res[i]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...