Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // ███▓▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓╬╬╬╬╬╬▓█
- // ███▓███████▓▓╬╬╬╬╬╬╬╬╬╬╬╬▓███▓▓▓▓█▓╬╬╬▓█
- // ███████▓█████▓▓╬╬╬╬╬╬╬╬▓███▓╬╬╬╬╬╬╬▓╬╬▓█
- // ████▓▓▓▓╬╬▓█████╬╬╬╬╬╬███▓╬╬╬╬╬╬╬╬╬╬╬╬╬█
- // ███▓▓▓▓╬╬╬╬╬╬▓██╬╬╬╬╬╬▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ████▓▓▓╬╬╬╬╬╬╬▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ███▓█▓███████▓▓███▓╬╬╬╬╬╬▓███████▓╬╬╬╬▓█
- // ████████████████▓█▓╬╬╬╬╬▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬█
- // ███▓▓▓▓▓▓▓╬╬▓▓▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ████▓▓▓╬╬╬╬▓▓▓▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ███▓█▓▓▓▓▓▓▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // █████▓▓▓▓▓▓▓▓█▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // █████▓▓▓▓▓▓▓██▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
- // █████▓▓▓▓▓████▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
- // ████▓█▓▓▓▓██▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
- // ████▓▓███▓▓▓▓▓▓▓██▓╬╬╬╬╬╬╬╬╬╬╬╬█▓╬▓╬╬▓██
- // █████▓███▓▓▓▓▓▓▓▓████▓▓╬╬╬╬╬╬╬█▓╬╬╬╬╬▓██
- // █████▓▓█▓███▓▓▓████╬▓█▓▓╬╬╬▓▓█▓╬╬╬╬╬╬███
- // ██████▓██▓███████▓╬╬╬▓▓╬▓▓██▓╬╬╬╬╬╬╬▓███
- // ███████▓██▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬████
- // ███████▓▓██▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓████
- // ████████▓▓▓█████▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█████
- // █████████▓▓▓█▓▓▓▓▓███▓╬╬╬╬╬╬╬╬╬╬╬▓██████
- // ██████████▓▓▓█▓▓▓╬▓██╬╬╬╬╬╬╬╬╬╬╬▓███████
- // ███████████▓▓█▓▓▓▓███▓╬╬╬╬╬╬╬╬╬▓████████
- // ██████████████▓▓▓███▓▓╬╬╬╬╬╬╬╬██████████
- // ███████████████▓▓▓██▓▓╬╬╬╬╬╬▓███████████
- #pragma GCC target("sse4,tune=native")
- #pragma GCC optimize("O3")
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- #include <numeric>
- #include <cstring>
- #include <ctime>
- #include <cstdlib>
- #include <set>
- #include <map>
- #include <unordered_map>
- #include <unordered_set>
- #include <list>
- #include <cmath>
- #include <bitset>
- #include <cassert>
- #include <queue>
- #include <deque>
- #include <cassert>
- #include <iomanip>
- #define pb push_back
- #define x first
- #define y second
- #define mp make_pair
- #define files(FILENAME) read(FILENAME); write(FILENAME)
- #define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
- #define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
- using namespace std;
- template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
- template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
- template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
- template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
- template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
- template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
- template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
- typedef long double base;
- typedef pair<base, base> point;
- const string FILENAME = "input";
- int n, p;
- void nsum(int &a, int b) {
- a += b;
- if (a >= p) a -= p;
- }
- int sum(int a, int b) {
- a += b;
- return a >= p ? a - p : a;
- }
- int mul(long long a, int b) {
- return a * b % p;
- }
- struct func {
- int A, B, C, D;
- func() {
- A = B = C = D = 0;
- }
- func(int x, int t) {
- D = t;
- C = mul(D, x);
- B = mul(C, x);
- A = mul(B, x);
- }
- void add() {
- A = sum(sum(A, D), mul(3, sum(B, C)));
- B = sum(B, sum(D, sum(C, C)));
- C = sum(C, D);
- }
- };
- func operator + (func a, func b) {
- nsum(a.A, b.A);
- nsum(a.B, b.B);
- nsum(a.C, b.C);
- nsum(a.D, b.D);
- return a;
- }
- const int MAXN = 1e5 + 1, SQRT = 340;
- int dp1[MAXN][SQRT];
- int dp2[MAXN][SQRT];
- func suf[MAXN];
- int main() {
- ios::sync_with_stdio(0);
- srand(time(0));
- //read(FILENAME);
- cin >> n >> p;
- dp1[0][0] = 1;
- for (int j = 1; j < SQRT; ++j) {
- for (int i = j; i <= n; ++i) {
- dp1[i][j] = sum(dp1[i - j][j], dp1[i - 1][j - 1]);
- }
- }
- for (int j = 1; j <= SQRT; ++j) {
- for (int i = j * (SQRT - 1); i <= n; ++i) {
- dp2[i][j] = dp1[i - j * (SQRT - 1)][j];
- }
- }
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= SQRT; ++j) {
- suf[i] = suf[i] + func(j, dp2[i][j]);
- }
- }
- for (int j = SQRT; --j;) {
- for (int i = j; i <= n; ++i) {
- auto v = suf[i - j];
- v.add();
- suf[i] = suf[i] + v;
- if (i == j) {
- suf[i].A++;
- suf[i].B++;
- suf[i].C++;
- suf[j].D++;
- }
- }
- }
- for (int i = 1; i <= n; ++i) {
- cout << suf[i].A % p << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement