結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | Ryuhei Mori |
提出日時 | 2021-01-20 02:57:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 3,764 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 39,936 KB |
実行使用メモリ | 6,144 KB |
最終ジャッジ日時 | 2024-05-10 04:14:07 |
合計ジャッジ時間 | 3,573 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
6,016 KB |
testcase_01 | AC | 41 ms
6,144 KB |
testcase_02 | AC | 40 ms
6,144 KB |
testcase_03 | AC | 40 ms
6,016 KB |
testcase_04 | AC | 39 ms
6,016 KB |
testcase_05 | AC | 40 ms
6,016 KB |
testcase_06 | AC | 40 ms
6,144 KB |
testcase_07 | AC | 39 ms
6,016 KB |
testcase_08 | AC | 40 ms
6,016 KB |
testcase_09 | AC | 40 ms
6,016 KB |
testcase_10 | AC | 40 ms
6,016 KB |
testcase_11 | AC | 40 ms
6,016 KB |
testcase_12 | AC | 40 ms
6,144 KB |
testcase_13 | AC | 40 ms
6,144 KB |
testcase_14 | AC | 41 ms
6,016 KB |
testcase_15 | AC | 40 ms
6,144 KB |
testcase_16 | AC | 30 ms
5,888 KB |
ソースコード
#include <utility> #include <unistd.h> struct IO { static const int bufsize=1<<23; char ibuf[bufsize], obuf[bufsize]; char *ip, *op; IO(): ip(ibuf), op(obuf) { for(int t = 0, k = 0; (k = read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t)) > 0; t+=k); } ~IO(){ for(int t = 0, k = 0; (k = write(STDOUT_FILENO, obuf+t, op-obuf-t)) > 0; t+=k); } long long scan_int(){ long long x=0; bool neg=false; for(;*ip<'+';ip++) ; if(*ip=='-'){ neg=true; ip++;} else if(*ip=='+') ip++; for(;*ip>='0';ip++) x = 10*x+*ip-'0'; if(neg) x = -x; return x; } void put_int(long long x, char c=0){ static char tmp[20]; if(x==0) *op++ = '0'; else { int i; if(x<0){ *op++ = '-'; x = -x; } for(i=0; x; i++){ tmp[i] = x % 10; x /= 10; } for(i--; i>=0; i--) *op++ = tmp[i]+'0'; } if(c) *op++ = c; } void put_double(double x, char c=0){ unsigned y; const int mask = (1<<24) - 1; put_int(x); *op++ = '.'; x = x - (int) x; if(x < 0) x = -x; y = x * (1<<24); for(int i=0;i<7;i++){ y *= 10; *op++ = '0' + (y>>24); y &= mask; } if(c) *op++ = c; } inline char scan_char(){ return *ip++; } inline void put_char(char c){ *op++ = c; } inline char *scan_string(){ char *s = ip; while(*ip!='\n'&&*ip!=' ') ip++; *ip++='\0'; return s;} inline void put_string(const char *s, char c=0){ while(*s) *op++=*s++; if(c) *op++=c;} } io; using u32 = unsigned int; using u64 = unsigned long long; template <u32 MOD> struct Mint { u32 n; constexpr Mint(u32 n = 0): n(n) {} constexpr Mint operator-() const { return Mint(n ? MOD - n: 0); } constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; } constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; } constexpr Mint &operator*=(const Mint &rhs){ n = (u64) n * rhs.n % MOD; return *this; } friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; } friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; } friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; } friend constexpr bool operator==(const Mint &lhs, const Mint &rhs){ return lhs.n == rhs.n; } friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs){ return lhs.n != rhs.n; } }; template <class T> T mypow(T a, u32 n){ T r = 1; for(; n; n >>= 1){ if(n&1) r *= a; a *= a; } return r; } template <u32 MOD> Mint<MOD> inv(Mint<MOD> a){ return mypow(a, MOD-2); } constexpr u32 mod = 1000000007; using mint = Mint<mod>; mint p; /* x / (1 - px - x^2) 1 - (2 + p^2) x + x^2 0 1 p p^2+1 -p / (p^2 + 4) 0 1 2p 3(p^2+1) -p / (p^2 + 4) 1 p p^2+1 p^3+2p 0 0 p 2(p^2+1) 3(p^3+2p) 2 / (p^2 + 4) 0 0 1 2p */ mint q[21]; std::pair<mint, mint> bostan_mori_msb(u64 n){ mint a = 0, b = 1; for(int i = 63 - __builtin_clzll(n); i; i--){ if(n & (1 << i)){ a += b; b *= q[i]; } else { b += a; a *= q[i]; } } if(n & 1){ a = b - a; b *= q[0]; } else { b = b - a; a *= q[0]; } return {a, b}; } int main(){ mint p = io.scan_int(); u32 Q = io.scan_int(); mint s = inv(p * p + 4); mint t = 2 * s; s *= -p; q[0] = p; q[1] = p * p + 2; for(u32 i = 2; i < sizeof(q)/sizeof(*q); i++) q[i] = q[i-1] * q[i-1] - 2; while(Q--){ u32 n = io.scan_int(); n -= 2; auto [a, b] = bostan_mori_msb(n); mint z = s * (1 + n) * a + t * n * b; io.put_int(z.n, '\n'); } return 0; }