結果
問題 | No.1419 Power Moves |
ユーザー | 👑 Nachia |
提出日時 | 2021-03-05 22:02:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 834 bytes |
コンパイル時間 | 3,911 ms |
コンパイル使用メモリ | 254,864 KB |
最終ジャッジ日時 | 2025-01-19 11:06:53 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:21:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 21 | scanf("%d%d",&N,&K); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) using mll=atcoder::static_modint<1000000007>; ull powm(ull a,ull i,ull m){ if(i==0) return 1; ull res=powm(a*a%m,i/2,m); if(i%2) res=res*a%m; return res; } int N,K; vector<mll> ans; int main(){ scanf("%d%d",&N,&K); int s = (1+N-powm(2,K,N))%N; vector<int> G; G.push_back(s); while((G.back()+2)%N!=s) G.push_back((G.back()+2)%N); int N2=G.size(); mll g = mll(2).pow(K).inv(); mll spread_mod = powm(2,K,N2)%N2; mll spread_times = (mll(2).pow(K)-spread_mod)/N2; vector<mll> ans2(N2,spread_times*g); rep(i,spread_mod.val()) ans2[i]+=g; ans.assign(N,mll(0)); rep(i,N2) ans[G[i]]=ans2[i]; rep(i,N) printf("%u\n",ans[i].val()); return 0; }