F. 多项式化简 --combinatorics,implementation

 1 

#include 
 2 using std::cin;
 3 using std::cout;
 4 using i64 = long long;
 5 const int N = 100;
 6 __int128 C[N][N];
 7 template<class T>
 8 struct fraction {
 9     fraction(T x = 0, T y = 1) :fz(x), fm(y) {
10         assert(y != 0);
11         reduct();
12     }
13     T fz, fm;
14     void reduct() {
15         T gcd_m = gcd(this->fz, this->fm);
16         this->fz = this->fz / gcd_m;
17         this->fm = this->fm / gcd_m;
18         if( this->fm < 0){
19             this->fz *= -1;this->fm *= -1;
20         }
21     }
22     T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
23     T lcm(T a, T b) { return a * 1ll * b / gcd(a, b); }
24     T ksm(T a, T n, i64 mod = 998244353) {
25         T res = 1;
26         for (; n; n /= 2, a = a * 1ll * a % mod) {
27             if (n % 2) res = res * 1ll * a % mod;
28         }return res;
29     }
30     T modulo(i64 mod = 998244353) {
31         return (this->fz % mod * ksm(this->fm, mod - 2) % mod + mod) % mod;
32     }
33     fraction operator+(const fraction& rhs) {
34         T common_div = lcm(this->fm, rhs.fm);
35         T fz1 = this->fz * (common_div / this->fm);
36         T fz2 = rhs.fz * (common_div / rhs.fm);
37         return { fz1 + fz2,common_div };
38     }
39     fraction operator-(const fraction& rhs) {
40         T common_div = lcm(this->fm, rhs.fm);
41         T fz1 = this->fz * (common_div / this->fm);
42         T fz2 = rhs.fz * (common_div / rhs.fm);
43         return { fz1 - fz2,common_div };
44     }
45     fraction operator*(const fraction& rhs) {
46         return { (this->fz) * (rhs.fz), (this->fm) * (rhs.fm) };
47     }
48     fraction operator/(const fraction& rhs) {
49         return { (this->fz) * (rhs.fm), (this->fm) * (rhs.fz) };
50     }
51 };
52 template<class T>
53 std::ostream& operator<< (std::ostream& os, const fraction& rhs) {
54     os << rhs.fz << "/" << rhs.fm;
55     return os;
56 }
57 template<class T>
58 std::istream& operator>> (std::istream& is, fraction& rhs) {
59     is >> rhs.fz >> rhs.fm; rhs.reduct();
60     return is;
61 }
62 template<class T>
63 inline void write(T x) {
64     if (x < 0) x = -x, putchar('-');
65     if (x > 9) write(x / 10);
66     putchar('0' + x % 10);
67 }
68 int main(){
69     std::ios::sync_with_stdio(false);
70     std::cin.tie(nullptr);
71     C[0][0] = 1;
72     for(int i = 1; i <= 70; i++){
73         C[i][0] = 1;
74         for(int j = 1; j <= i; j++){
75             C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
76         }
77     }
78     
79     int n;    
80     cin >> n;
81     std::vector> v(n + 1,{0,1});
82     for(int i = 0; i * 2 <= n; i++){
83         v[n - 2 * i].fz = C[2*(n - i)][n] * C[n][i] * ((i & 1) ? (-1):1);
84         v[n - 2 * i].fm = (1 << n);
85         v[n - 2 * i].reduct();
86     }
87     for(int i = n; i >= 0; i--){
88         if(v[i].fz == 0){
89             write(0);
90             putchar(' ');
91             continue;
92         }
93         write(v[i].fz);
94         putchar('/');
95         write(v[i].fm);
96         putchar(' ');
97     }
98     return 0;
99 }