結果
問題 | No.1419 Power Moves |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:40:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 226 ms / 2,000 ms |
コード長 | 1,263 bytes |
コンパイル時間 | 970 ms |
コンパイル使用メモリ | 84,188 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-07 01:06:27 |
合計ジャッジ時間 | 7,060 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <iostream>#include <set>#include <map>#include <cmath>#include <queue>#include <vector>#include <string>#include <algorithm>#include <functional>using namespace std;long long modpow(long long a, long long b, long long m) {long long p = 1, q = a;for (int i = 0; i < 32; i++) {if ((b / (1LL << i)) % 2LL == 1) {p *= q; p %= m;}q *= q; q %= m;}return p;}long long Div(long long a, long long b, long long m) {return (a * modpow(b, m - 2, m)) % m;}long long mod = 1000000007;long long N, K;long long Answer1[1 << 18];long long Answer2[1 << 18];int main() {cin >> N >> K;long long T = modpow(2, K - 1, mod);// 前半組long long U1 = modpow(2, K - 1, N);long long U2 = Div((T - U1 + mod) % mod, N, mod);for (int i = 0; i < N; i++) Answer1[i] += U2;for (int i = 0; i < U1; i++) Answer1[i] += 1;// 後半組for (int i = 0; i < N; i++) Answer1[i] += U2;for (int i = N - 1; i >= N - U1; i--) Answer1[i] += 1;// 答えを合わせるfor (int i = 0; i < N; i++) {Answer2[(2 * i + 1) % N] += Answer1[i];Answer2[(2 * i + 1) % N] %= mod;}// 出力long long Patterns = modpow(2, K, mod);for (int i = 0; i < N; i++) {cout << Div(Answer2[i], Patterns, mod) << endl;}return 0;}