結果
問題 | No.1419 Power Moves |
ユーザー |
👑 ![]() |
提出日時 | 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;}