結果
問題 | No.2396 等差二項展開 |
ユーザー |
![]() |
提出日時 | 2023-07-28 22:47:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 6,000 ms |
コード長 | 1,334 bytes |
コンパイル時間 | 3,885 ms |
コンパイル使用メモリ | 255,780 KB |
最終ジャッジ日時 | 2025-02-15 20:37:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;typedef modint mint;typedef long long ll;#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)template <typename T> bool chmin(T &a, const T &b) {if (a <= b) return false;a = b;return true;}template <typename T> bool chmax(T &a, const T &b) {if (a >= b) return false;a = b;return true;}// (m : FREE) [x^(N-K)] (1+x)^N / (1-Mx^L)// 繰り返し二乗しながら巡回畳み込みint main(){ios_base::sync_with_stdio(false);cin.tie(NULL);ll n, m; cin >> n >> m;int l; cin >> l;int k; cin >> k;ll b; cin >> b;mint::set_mod(b);if (b==1){cout << 0 << '\n';return 0;}if (l==1){cout << mint(1+m).pow(n).val() << '\n';return 0;}vector<mint> f(l);vector<mint> tar(l);f[0] = 1;tar[0] = 1;tar[1] = 1;rep(i,0,60){if (n >> i & 1){vector<mint> g(2*l-1);rep(i,0,l){rep(j,0,l){g[i+j] += f[i] * tar[j];}}rep(i,l,2*l-1){g[i%l] += g[i] * m;}f = g;}vector<mint> t2(2*l-1);rep(i,0,l){rep(j,0,l){t2[i+j] += tar[i] * tar[j];}}rep(i,l,2*l-1){t2[i%l] += t2[i] * m;}t2.resize(l);tar = t2;}cout << f[k].val() << '\n';}