Submission #19002

# Submission time Handle Problem Language Result Execution time Memory
19002 2016-02-17T02:53:46 Z kriii 비트 (kriii4_Q) C++14
100 / 100
205 ms 1912 KB
```#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];
}
}

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;
}
}
}
}

vector<long long> res = gauss(A);
for (int i=1;i<=N;i++) printf ("%lld\n",res[i]);

return 0;
}```

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1776 KB Output is correct
2 Correct 6 ms 1780 KB Output is correct
3 Correct 0 ms 1776 KB Output is correct
4 Correct 0 ms 1780 KB Output is correct
5 Correct 9 ms 1904 KB Output is correct
6 Correct 0 ms 1776 KB Output is correct
7 Correct 0 ms 1776 KB Output is correct
8 Correct 5 ms 1780 KB Output is correct
9 Correct 0 ms 1776 KB Output is correct
10 Correct 0 ms 1772 KB Output is correct
11 Correct 0 ms 1776 KB Output is correct
12 Correct 6 ms 1776 KB Output is correct
13 Correct 0 ms 1772 KB Output is correct
14 Correct 4 ms 1772 KB Output is correct
15 Correct 9 ms 1904 KB Output is correct
16 Correct 0 ms 1776 KB Output is correct
17 Correct 2 ms 1780 KB Output is correct
18 Correct 5 ms 1780 KB Output is correct
19 Correct 10 ms 1908 KB Output is correct
20 Correct 0 ms 1776 KB Output is correct

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1776 KB Output is correct
2 Correct 173 ms 1912 KB Output is correct
3 Correct 4 ms 1772 KB Output is correct
4 Correct 27 ms 1780 KB Output is correct
5 Correct 92 ms 1772 KB Output is correct
6 Correct 179 ms 1908 KB Output is correct
7 Correct 8 ms 1780 KB Output is correct
8 Correct 43 ms 1780 KB Output is correct
9 Correct 118 ms 1776 KB Output is correct
10 Correct 19 ms 1772 KB Output is correct
11 Correct 75 ms 1780 KB Output is correct
12 Correct 193 ms 1908 KB Output is correct
13 Correct 4 ms 1780 KB Output is correct
14 Correct 25 ms 1772 KB Output is correct
15 Correct 86 ms 1776 KB Output is correct
16 Correct 0 ms 1776 KB Output is correct
17 Correct 7 ms 1776 KB Output is correct
18 Correct 141 ms 1908 KB Output is correct
19 Correct 0 ms 1772 KB Output is correct
20 Correct 205 ms 1912 KB Output is correct