yukicoder-474

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/474 No.474 色塗り２] ==

=== Description ===

{{{
#!html
<p>考虑这样一棵深度为$2$的有根树：根节点有$A$个儿子，根节点的每个儿子有$B$个儿子。如下是$A=3,B=2$的一个有根树：<br>
<img src="http://10.71.10.90/zimpha/images/yukicoder-474-1.png"/>
</p>

<p>现在用$C$中颜色给这棵树的节点染色，问本质不同的方案数$\bmod 2$的值。如果重新安排儿子的顺序染色一样，那么这两种方案就是一样的。如下是$A=3,B=2$的一些染色方案：<br>
<img src="http://10.71.10.90/zimpha/images/yukicoder-474-2.png"/>
</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$T$<br>
$A_1$ $B_1$ $C_1$<br>
$A_2$ $B_2$ $C_2$<br>
$\vdots$<br>
$A_T$ $B_T$ $C_T$<br>
</p>
<p>
$1 \leq T \leq 10^{5}, 1 \le A_i, B_i, C_i \le 10^6$。
</p>
}}}

=== Output ===

{{{
#!html
<p>每组数据输出方案数$\bmod 2$。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
4
2 2 2
1 1 999999
1000000 1000000 1
31415 9265 35897
</pre>
}}}
输出
{{{
#!html
<pre>
0
1
1
0
</pre>
}}}

No.474 色塗り２

Description

考虑这样一棵深度为$2$的有根树：根节点有$A$个儿子，根节点的每个儿子有$B$个儿子。如下是$A=3,B=2$的一个有根树：

现在用$C$中颜色给这棵树的节点染色，问本质不同的方案数$\bmod 2$的值。如果重新安排儿子的顺序染色一样，那么这两种方案就是一样的。如下是$A=3,B=2$的一些染色方案：

Input

$T$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_T$ $B_T$ $C_T$

$1 \leq T \leq 10^{5}, 1 \le A_i, B_i, C_i \le 10^6$。

Output

每组数据输出方案数$\bmod 2$。

Sample

Sample 1

输入

42 2 21 1 9999991000000 1000000 131415 9265 35897

输出