結果
問題 | No.1419 Power Moves |
ユーザー |
![]() |
提出日時 | 2021-03-05 22:45:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 1,562 bytes |
コンパイル時間 | 1,456 ms |
コンパイル使用メモリ | 171,932 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-07 03:37:26 |
合計ジャッジ時間 | 5,837 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll,ll> P; typedef vector<ll> VI; typedef vector<VI> VVI; #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() constexpr ll MOD=1000000007; constexpr ll INF=2e18; ll power(ll x, ll y, ll m){ x%=m; ll ret=1; while(y){ if(y&1) ret=ret*x%m; x=x*x%m; y>>=1; } return ret; } ll divid(ll x, ll y){ x%=MOD; return x*power(y,MOD-2,MOD)%MOD; } int main(){ ll n, k; cin >> n >> k; ll d=power(2,k-1,MOD); VI ans(n,0); if(n%2==0){ ll r=power(2,k-1,n/2); ll a=divid(d-r+MOD,n/2); REP(i,n/2){ if(i<r) ans[i*2+1]=(ans[i*2+1]+a+1)%MOD; else ans[i*2+1]=(ans[i*2+1]+a)%MOD; if(n/2-i-1<r) ans[i*2+1]=(ans[i*2+1]+a+1)%MOD; else ans[i*2+1]=(ans[i*2+1]+a)%MOD; } REP(i,n) cout << divid(ans[i],d*2) << endl; } else{ ll r=power(2,k-1,n); ll a=divid(d-r+MOD,n); REP(i,n){ if(i<r) ans[(i*2+1)%n]=(ans[(i*2+1)%n]+a+1)%MOD; else ans[(i*2+1)%n]=(ans[(i*2+1)%n]+a)%MOD; } REP(i,n){ if(i<r) ans[(2*n-(i*2+1))%n]=(ans[(2*n-(i*2+1))%n]+a+1)%MOD; else ans[(2*n-(i*2+1))%n]=(ans[(2*n-(i*2+1))%n]+a)%MOD; } REP(i,n) cout << divid(ans[i],d*2) << endl; } return 0; }