包除原理
包除原理とド・モルガンの法則使って求めるやつ。 包除原理 - Wikipedia 六面サイコロを考える。つまりK=6として、出目の和が7になるペアは(1, 6), (2, 5), (3, 4)の3種類。これらのペアが一つもできない場合を求めたい。すべての出目の組をUとし、それぞれ…
公式解説動画のとおりに実装。 ちなみに22k mod p (pは素数)はフェルマーの小定理より 22k mod (p-1) mod p で求まる。 vector<vi> dp; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); int N, M; while (cin >> N ></vi>…