結果

問題 No.1448 和差算
コンテスト
ユーザー tnakao0123
提出日時 2021-04-01 13:01:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,722 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 96,296 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-17 17:04:06
合計ジャッジ時間 1,832 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1448.cc:  No.1448 和差算 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MOD = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

int as[2], bs[2];
ll ps[4];

/* subroutines */

int powmod(int a, ll n) {  // a^n % MOD
  int pm = 1;
  while (n > 0) {
    if (n & 1) pm = (ll)pm * a % MOD;
    a = (ll)a * a % MOD;
    n >>= 1;
  }
  return pm;
}

/* main */

int main() {
  ll n;
  scanf("%d%d%d%d%lld", as, as + 1, bs, bs + 1, &n);

  /*
    a{i+1}=ai-bi, b{i+1}=ai+bi
    ->
    a{i+1}+b{i+1}=(ai-bi)+(ai+bi)=2ai
    a{i+1}-b{i+1}=(ai-bi)-(ai+bi)=-2bi
    a{i+2}+b{i+2}=2a{i+1}=2(ai-bi)
    a{i+2}-b{i+2}=-2b{i+1}=-2(ai+bi)
    a{i+3}+b{i+3}=2(a{i+1}-b{i+1})=2((ai-bi)-(ai+bi))=-4bi
    a{i+3}-b{i+3}=-2(a{i+1}+b{i+1})=-2((ai-bi)+(ai-bi))=-4ai
    a{i+4}+b{i+4}=-4b{i+1}=-4(ai+bi)
    a{i+4}-b{i+4}=-4a{i+1}=-4(ai-bi)
    ->
    let n=4m+k (0<=k<4)
    an+bn = (-4)^m*(ak+bk)
   */

  int k = n & 3;
  ll m = n >> 2;

  for (int bits = 0; bits < 4; bits++) {
    ll ai = as[bits >> 1], bi = bs[bits & 1];
    for (int i = 0; i < k; i++) {
      ll a1 = ai - bi, b1 = ai + bi;
      ai = a1, bi = b1;
    }
    ps[bits] = ai + bi;
  }
  sort(ps, ps + 4);

  int ab = ((m & 1) ? ps[0] : ps[3]) % MOD;
  if (ab < 0) ab += MOD;

  int e = powmod(4, m);
  int x = (ll)((m & 1) ? (MOD - e) : e) * ab % MOD;
  printf("%d\n", x);
  return 0;
}
0