alan23273850 的刷題筆記
d311: 數學少女的難題
Tags: polynomial
出處：https://zerojudge.tw/ShowProblem?problemid=d311
提交：https://zerojudge.tw/Submissions?problemid=d311&account=allllllan123456
問題：請求出從 1 到 $n\in[1,1000]$ 之中任取 $m\in[1,n]$ 個相異數的乘積之和。因為答案可能很大，所以先 mod 1572869 再輸出即可。
解法：如果對多項式係數熟悉的人便可以馬上聯想到這一題 d437，事實上本題的答案根本就是多項式 $(x+1)(x+2)…(x+n)$ 展開之後從高次項數下來的第 $m$ 個係數。又因為同餘的環境在加、減、乘的運算底下仍能保有正確性，在計算過程中我們可以隨時對任何一個係數取 mod 1572869 也不影響到正確性。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n, m, coL=1; long long co[1001] = {1};
6 cin >> n >> m;
7 while (n--) {
8 int r = n + 1;
9 co[coL] = r * co[coL-1] % 1572869;
10 for (int i=coL-1; i>0; i--)
11 co[i] = (co[i] + co[i-1] * r) % 1572869;
12 coL++;
13 }
14 cout << co[m] << '\n';
15 return 0;
16}