Placing Stones
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
现有A,B两堆石子,初始时分别有粒。每次可以执行如下两种操作之一:
(1)将A堆中一半(向下取整,下同)的石子加到B堆中,然后在A堆上补加一粒石子;
(2)将B堆中一半的石子加到A堆中,然后在B堆上补加一粒石子。
要求若干次操作之后,两堆的石子数分别变为,求共有多少种操作方案。
I/O格式
输入
第一行是一个正整数,表示数据的组数;
之后行,每行一组测试数据,包含4个正整数,保证。
输出
每组数据输出一行,方案数对取模后的结果。
样例
输入
输出
数据规模及约定
50%的数据:
100%的数据:
时间限制1s,空间限制256MB。