#include #include #define ll long long int #define pb push_back #define st first #define nd second #define pii pair #define mp make_pair #define pll pair #define ld long double #define ull unsigned long long #define double float using namespace std; // taken from https://github.com/ShahjalalShohag/code-library/blob/master/Math/NTT.cpp const int mod = 167772161; const double PI = acos(-1); struct base { double a, b; base(double a = 0, double b = 0) : a(a), b(b) {} const base operator + (const base &c) const { return base(a + c.a, b + c.b); } const base operator - (const base &c) const { return base(a - c.a, b - c.b); } const base operator * (const base &c) const { return base(a * c.a - b * c.b, a * c.b + b * c.a); } }; void fft(vector &p, bool inv = 0) { int n = p.size(), i = 0; for(int j = 1; j < n - 1; ++j) { for(int k = n >> 1; k > (i ^= k); k >>= 1); if(j < i) swap(p[i], p[j]); } for(int l = 1, m; (m = l << 1) <= n; l <<= 1) { double ang = 2 * PI / m; base wn = base(cos(ang), (inv ? 1. : -1.) * sin(ang)), w; for(int i = 0, j, k; i < n; i += m) { for(w = base(1, 0), j = i, k = i + l; j < k; ++j, w = w * wn) { base t = w * p[j + l]; p[j + l] = p[j] - t; p[j] = p[j] + t; } } } if(inv) for(int i = 0; i < n; ++i) p[i].a /= n, p[i].b /= n; } vector multiply(vector &a, vector &b) { int n = a.size(), m = b.size(), t = n + m - 1, sz = 1; while(sz < t) sz <<= 1; vector x(sz), y(sz), z(sz); for(int i = 0 ; i < sz; ++i) { x[i] = i < (int)a.size() ? base(a[i], 0) : base(0, 0); y[i] = i < (int)b.size() ? base(b[i], 0) : base(0, 0); } fft(x), fft(y); for(int i = 0; i < sz; ++i) z[i] = x[i] * y[i]; fft(z, 1); vector ret(sz); for(int i = 0; i < sz; ++i) ret[i] = (int) (z[i].a + 0.5); while((int)ret.size() > 1 && ret.back() == 0) ret.pop_back(); return ret; } const int nax = 405; int wagi[nax]; int pref[nax][nax][nax]; int suf[nax][nax][nax]; int ans[nax][nax]; void solve(){ //int n; cin >> n; //int k; cin >> k; //for(int i=1;i<=n;i++) cin >> wagi[i]; int n = 400; int k = 400; for(int i=1;i<=n;i++) wagi[i] = i; pref[0][0][0] = 1; suf[n + 1][0][0] = 1; for(int i=1;i<=n;i++){ for(int j=0;j<=i;j++){ for(int c=0;c<=k;c++){ pref[i][j][c] = pref[i - 1][j][c]; if(j >= 1 && c >= wagi[i]){ pref[i][j][c] += pref[i - 1][j - 1][c - wagi[i]]; if(pref[i][j][c] >= mod) pref[i][j][c] -= mod; } } } } for(int i=n;i>=1;i--){ for(int j=0;j<=n-i+1;j++){ for(int c=0;c<=k;c++){ suf[i][j][c] = suf[i + 1][j][c]; if(j >= 1 && c >= wagi[i]){ suf[i][j][c] += suf[i + 1][j - 1][c - wagi[i]]; if(suf[i][j][c] >= mod) suf[i][j][c] -= mod; } } } } vector tmp; for(int s=1;s<=n;s++){ for(int WL=0;WL<=k;WL++){ vector one, two; for(int c=0;c= co) continue; two[ile] += suf[s + 1][ile][w]; if(two[ile] >= mod) two[ile] -= mod; } } } else{ two = tmp; int bylo = hi + 1; int nowe = lo; for(int ile=0;ile= 0 && bylo < co){ two[ile] -= suf[s + 1][ile][bylo]; if(two[ile] < 0) two[ile] += mod; } if(nowe >= 0 && nowe < co){ two[ile] += suf[s + 1][ile][nowe]; if(two[ile] >= mod) two[ile] -= mod; } } } tmp = two; auto c = multiply(one, two); for(int j=0;j= mod) ans[s][j] -= mod; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=n-1;j++) cout << ans[i][j] << " "; cout << "\n"; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) solve(); return 0; } //C:\Users\Przemek\Desktop\PROJEKCIK\ctu