結果

問題 No.474 色塗り２
ユーザー snukesnuke
提出日時 2016-12-22 17:39:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 91 ms / 2,000 ms
コード長 1,780 bytes
コンパイル時間 1,385 ms
コンパイル使用メモリ 160,420 KB
実行使用メモリ 52,932 KB
最終ジャッジ日時 2024-12-14 14:30:18
合計ジャッジ時間 2,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
52,932 KB
testcase_01 AC 36 ms
52,676 KB
testcase_02 AC 36 ms
52,804 KB
testcase_03 AC 91 ms
52,932 KB
testcase_04 AC 35 ms
52,932 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:46:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |   scanf("%d",&ts);
      |   ~~~~~^~~~~~~~~~
main.cpp:64:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |     scanf("%d%d%d",&a,&b,&c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define fi first
#define se second
using namespace std;
typedef long long int ll;

// mod
const int K = 20;
const int mod = 1<<K;
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
};
mint ex(mint a, ll t) {
  if(!t) return 1;
  mint res = ex(a,t/2);
  res *= res;
  return (t&1)?res*a:res;
}
//

typedef pair<mint,int> P;
P p[mod*2];
mint ip[mod*2];

mint inv(mint a) { return ex(a,mod/2-1);}
mint comb(int a, int b) {
  int c = a-b;
  int two = p[a].se-p[b].se-p[c].se;
  if (two >= K) return 0;
  mint res = p[a].fi*ip[b]*ip[c];
  res *= 1<<two;
  return res;
}

int main() {
  int ts;
  scanf("%d",&ts);
  assert(1 <= ts && ts <= 100000);
  p[0] = P(1,0);
  for (int i = 1; i < mod*2; ++i) {
    p[i] = p[i-1];
    int x = i;
    while (x%2 == 0) p[i].se++, x >>= 1;
    p[i].fi *= x;
  }
  ip[mod*2-1] = inv(p[mod*2-1].fi);
  for (int i = mod*2-1; i >= 1; --i) {
    ip[i-1] = ip[i];
    int x = i;
    while (x%2 == 0) x >>= 1;
    ip[i-1] *= x;
  }
  while (ts--) {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    assert(1 <= a && a <= 1000000);
    assert(1 <= b && b <= 1000000);
    assert(1 <= c && c <= 1000000);
    // C(C(c+b-1,b)*c+a-1,a)*c
    mint x = comb(c+b-1,b)*c;
    x = x+a-1;
    int ans = ((x.x&a)==a)&c;
    printf("%d\n", ans);
  }
  return 0;
}
0