結果
問題 | No.1419 Power Moves |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:53:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 1,625 bytes |
コンパイル時間 | 3,182 ms |
コンパイル使用メモリ | 182,336 KB |
最終ジャッジ日時 | 2025-01-19 10:56:00 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;using lll=__int128_t;ll powmod(ll a, ll k, ll MOD){lll ap=a, ans=1;while(k){if(k&1){ans*=ap;ans%=MOD;}ap=ap*ap;ap%=MOD;k>>=1;}return (ll)ans;}using mint=modint1000000007;int n;int k;int main(){cin>>n>>k;const ll MOD=1e9+7;mint ans1[100010];if(n%2==0){int r=powmod(2, k-1, n/2);for(int i=0; i<r; i++) ans1[2*i+1]+=1;mint x=(mint(2).pow(k-1)-r)/mint(n/2);for(int i=1; i<n; i+=2){ans1[i]+=x;}}else{int r=powmod(2, k-1, n);for(int i=0; i<r; i++) ans1[(2*i+1)%n]+=1;mint x=(mint(2).pow(k-1)-r)/mint(n);for(int i=0; i<n; i++){ans1[i]+=x;}}mint ans[100010];for(int i=0; i<n; i++){ans[i]+=ans1[i];ans[(n-i)%n]+=ans1[i];}mint y=mint(2).pow(k).inv();for(int i=0; i<n; i++){ans[i]*=y;cout<<ans[i].val()<<endl;}return 0;}