Language: C++

double pro[11][200];
 
typedef vector<vector<double> > mat;
 
 
mat matmul(const mat& a,const mat& b){
  int n = SZ(a);
  mat c(n,vector<double>(n));
 
  rep(i,n)rep(j,n)rep(k,n)
    c[i][j] += a[i][k] * b[k][j];
  return c;
}
 
mat powmat(mat a, int p){
  int n=SZ(a);
  mat ret(n,vector<double>(n));
  rep(i,n) ret[i][i] = 1;
  while(p){
    if(p&1) ret=matmul(ret,a);
    a=matmul(a,a);
    p >>= 1;
  }
  return ret;
}
 
vector<double> gausu(mat A, vector<double> b){
  int n=SZ(A);
  vector<double> ret(n);
 
  rep(i,n){
    double maxv=abs(A[i][i]);
    int idx = i;
    for(int j=i+1;j<n;++j){
      if(maxv<abs(A[j][i])){
        maxv = abs(A[j][i]);
        idx = j;
      }
    }
    swap(A[i],A[idx]);
    swap(b[i],b[idx]);
    maxv = A[i][i];
    for(int j=0;j<n;++j){
      if(j==i) continue;
      double mul = A[j][i]/maxv;
      b[j] -= mul * b[i];     
      for(int k=i;k<n;++k)
        A[j][k] -= mul * A[i][k];
    }
  }
  rep(i,n) ret[i] = b[i]/A[i][i];
  return ret;
}
 
int main(){
  int s,n,k;
  cin >> s >> n >> k;
  s=abs(s);
  if(n==1){
    if(s%k) cout << -1 << endl;
    else cout << s/k << endl;
    return 0;
  }
 
  pro[0][0] = 1;
  for(int i=0;i<k;++i)
    for(int j=1;j<=n;++j)
      for(int idx=0;idx<=n*k;++idx)
        pro[i+1][idx+j] += pro[i][idx]/n;
   
  mat E(n*k+1,vector<double>(n*k+1));
  vector<double> eb(n*k+1,-1);
  eb[0] = 0;
 
  rep(x,n*k+1){
    if(x==0){
      E[0][0]=1;
      continue;
    }
    E[x][x] -= 1;
    rep(i,n*k){
      int idx=abs((x)-(i+1));
      E[x][idx] += pro[k][i+1];
    }
  }
  vector<double> ex(gausu(E,eb));
   
  if(n*k>=s){
    cout << ex[s] << endl;
    return 0;
  }
 
 
  double dp[10000]={0};
  for(int i=0;i<=n*k;++i)
    dp[i] = ex[i];
 
  for(int j=n*k+1;j<10000;++j)
    for(int i=k;i<=n*k;++i)
      dp[j] += (dp[j-i]+1) * pro[k][i];
 
  /*
  if(s<8000){
    cout << dp[s] << endl;
    return 0;
  }
  */
   
  mat A(n*k+1,vector<double>(n*k+1));
  rep(i,n*k) A[0][i] = pro[k][i+1];
  rep(i,n*k-1) A[i+1][i] = 1;
  A[0][n*k]=1;
  A[n*k][n*k]=1;
 
  vector<double> b(n*k+1);
  b[0] = b[n*k] = 1;
 
 
     
 
  A=powmat(A,s-n*k);
   
  double ans = 0;
  ex[0] = 1;
  rep(i,n*k+1)
    ans += ex[n*k-i] * A[0][i];
  printf("%.8f\n",ans);
 
}

Compiler output:
a.cc:3:9: error: 'vector' does not name a type
    3 | typedef vector<vector<double> > mat;
      |         ^~~~~~
a.cc:6:1: error: 'mat' does not name a type
    6 | mat matmul(const mat& a,const mat& b){
      | ^~~
a.cc:15:1: error: 'mat' does not name a type
   15 | mat powmat(mat a, int p){
      | ^~~
a.cc:27:1: error: 'vector' does not name a type
   27 | vector<double> gausu(mat A, vector<double> b){
      | ^~~~~~
a.cc: In function 'int main()':
a.cc:57:3: error: 'cin' was not declared in this scope
   57 |   cin >> s >> n >> k;
      |   ^~~
a.cc:58:5: error: 'abs' was not declared in this scope
   58 |   s=abs(s);
      |     ^~~
a.cc:60:13: error: 'cout' was not declared in this scope
   60 |     if(s%k) cout << -1 << endl;
      |             ^~~~
a.cc:60:27: error: 'endl' was not declared in this scope
   60 |     if(s%k) cout << -1 << endl;
      |                           ^~~~
a.cc:61:10: error: 'cout' was not declared in this scope
   61 |     else cout << s/k << endl;
      |          ^~~~
a.cc:61:25: error: 'endl' was not declared in this scope
   61 |     else cout << s/k << endl;
      |                         ^~~~
a.cc:71:3: error: 'mat' was not declared in this scope
   71 |   mat E(n*k+1,vector<double>(n*k+1));
      |   ^~~
a.cc:72:3: error: 'vector' was not declared in this scope
   72 |   vector<double> eb(n*k+1,-1);
      |   ^~~~~~
a.cc:72:10: error: expected primary-expression before 'double'
   72 |   vector<double> eb(n*k+1,-1);
      |          ^~~~~~
a.cc:73:3: error: 'eb' was not declared in this scope
   73 |   eb[0] = 0;
      |   ^~
a.cc:75:7: error: 'x' was not declared in this scope
   75 |   rep(x,n*k+1){
      |       ^
a.cc:75:3: error: 'rep' was not declared in this scope
   75 |   rep(x,n*k+1){
      |   ^~~
a.cc:86:10: error: expected primary-expression before 'double'
   86 |   vector<double> ex(gausu(E,eb));
      |          ^~~~~~
a.cc:89:5: error: 'cout' was not declared in this scope
   89 |     cout << ex[s] << endl;
      |     ^~~~
a.cc:89:13: error: 'ex' was not declared in this scope
   89 |     cout << ex[s] << endl;
      |             ^~
a.cc:89:22: error: 'endl' was not declared in this scope
   89 |     cout << ex[s] << endl;
      |                      ^~~~
a.cc:96:13: error: 'ex' was not declared in this scope
   96 |     dp[i] = ex[i];
      |             ^~
a.cc:109:6: error: expected ';' before 'A'
  109 |   mat A(n*k+1,vector<double>(n*k+1));
      |      ^~
      |      ;
a.cc:110:7: error: 'i' was not declared in this scope
  110 |   rep(i,n*k) A[0][i] = pro[k][i+1];
      |       ^
a.cc:112:3: error: 'A' was not declared in this scope
  112 |   A[0][n*k]=1;
      |   ^
a.cc:115:10: error: expected primary-expression before 'double'
  115 |   vector<double> b(n*k+1);
      |          ^~~~~~
a.cc:116:3: error: 'b' was not declared in this scope
  116 |   b[0] = b[n*k] = 1;
      |   ^
a.cc:121:5: error: 'powmat' was not declared in this scope
  121 |   A=powmat(A,s-n*k);
      |     ^~~~~~
a.cc:124:3: error: 'ex' was not declared in this scope
  124 |   ex[0] = 1;
      |   ^~
a.cc:127:3: error: 'printf' was not declared in this scope
  127 |   printf("%.8f\n",ans);
      |   ^~~~~~
a.cc:1:1: note: 'printf' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
  +++ |+#include <cstdio>
    1 | double pro[11][200];