T1
题目描述
\(Mr.Hu\) 开了个饭店，来了两位客人：\(Alice\) 和 \(Bob\)，他们吃完饭要结账时，发现他们需要支付 \(c\) 元钱，但是 \(Alice\) 只有面值为 \(a\) 的钱，\(Bob\) 只有面值为 \(b\) 的钱（他们每个人的钱的和都大于 \(c\), 即可以认为他们有无数张对应面值钱）。现在，\(Mr.Hu\) 想知道，他们可能刚好支付完饭钱吗？如果可能，那么有多少种方式？你还需要计算出他们所有可能的支付方式的支付的钱的张数的和。
输入格式
第 \(1\) 行包含 \(2\) 个整数：\(T, opt\)，其中 \(T\) 表示数据组数，\(opt\) 为数据类型。
接下来 \(T\) 行，每行 \(3\) 个整数：\(a, b, c\)。
输出格式
对于每组数据：
-
如果 \(opt = 1\)，输出一行，包含一个整数：\(A\)，其中 \(A\) 表示刚好支付的方案数。
-
如果 \(opt = 2\)，输出一行，包含两个整数：\(A, B\)，其中 \(A\) 表示刚好支付的方案数，\(B\) 表示所有可能
支付方式的张数和。
输入样例1
2 2
3 4 21
2 4 12
输出样例1
2 13
4 18
样例1解释
对于 \(3, 4, 21\)，一共有两种可能的支付方式，分别是：\((3, 3), (7, 0)^1\)，所以 \(A\) 为 \(2\)，\(B\) 为 \(3 + 3 + 7 + 0 = 13\)。
对于 \(2, 4, 12\)，一共有四种可能的支付方式，分别是：\((6, 0), (4, 1), (2, 2), (0, 3)\)，所以 \(A\) 为 \(4\)，\(B\) 为
\(6 + 0 + 4 + 1 + 2 + 2 + 0 + 3 = 18\)。
输入样例2
2 1
3 4 21
2 4 12
输出样例2
2
4
数据规模
对于 \(20\%\) 数据，\(1 \leq a, b, c \leq 10000, 1 \leq T \leq 1000\)。
对于另外 \(40\%\) 数据，\(1 \leq a, b, c \leq 10^9\)，其中 \(opt = 1\)。
对于另外 \(40\%\) 数据，\(1 \leq a, b, c \leq 10^9\)，其中 \(opt = 2\)。
对于 \(100\%\) 数据，\(1 \leq T \leq 10^5, 1 \leq opt \leq 2\)。
题解
设 \(Alice\) 要支付的钱的张数为 \(x\) (\(x \geq 0\))，\(Bob\) 要支付的钱的张数为 \(y\) (\(y \geq 0\))，那么可以写出如下二元一次不定方程 \(ax + by = c\)，根据数论学习笔记（一）（2024.7.25），当且仅当 \(\gcd(a, b) \mid c\) 时才有解。
考虑 \(x\) 和 \(y\) 都要大于 \(0\)，那么将 \(x\) 变为最小的满足条件的非负整数时，如果 \(y\) 仍未非正整数，那么也是凑不出这么多钱的。
以上两种情况是无解的，直接输出 \(0\)，如果有 \(x\) 和 \(y\) 都为非负整数的解，那么考虑通解 \(x = x_0 + (b / d)n, y = y_0 - (a / d)n\)。
考虑到将 \(x\) 变为最小值时 \(y\) 已是最大值，所以 \(\lfloor\displaystyle\frac{y}{a / d}\rfloor + 1\) (加 \(1\) 是因为可以一个 \(a / d\) 也不减) 就是方案数。
考虑每变化一次张数会变大或变小 \(| a / d - b / d |\)，且要么一直变大，要么一直变小，可以发现这是一个等差数列，所以只需要将总张数最大和总张数最小的情况算出，就可以套用等差数列求和公式来求解张数。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int extend_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;
return 0;
}
int d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
int T, opt, a, b, c;
signed main(){
freopen("pay.in", "r", stdin);
freopen("pay.out", "w", stdout);
scanf("%lld%lld", &T, &opt);
while(T--){
scanf("%lld%lld%lld", &a, &b, &c);
if(c % gcd(a, b) != 0){
if(opt == 1)
printf("0\n");
else
printf("0 0\n");
continue;
}
int d = gcd(a, b);
int x, y;
extend_gcd(a, b, x, y);
x *= c / d;
y *= c / d;
int dis;
if(x < 0){
dis = ceil((-x) * 1.0 / (b / d));
x += dis * (b / d);
y -= dis * (a / d);
} else {
dis = floor(x * 1.0 / (b / d));
x -= dis * (b / d);
y += dis * (a / d);
}
if(y >= 0){
printf("%lld", y / (a / d) + 1);
if(opt == 1)
printf("\n");
else {
printf(" ");
int ans1 = x + y, ans2 = y % (a / d) + x + y / (a / d) * (b / d);
int ans = (ans1 + ans2) * (y / (a / d) + 1) / 2;
printf("%lld\n", ans);
}
} else {
if(opt == 1)
printf("0\n");
else
printf("0 0\n");
continue;
}
}
return 0;
}
T2
题目描述
\(Mr.Hu\) 被传送到了一个无限大的表格上，现在这个表格的第 \(i\) 行第 \(j\) 列的值是 \(a_{i,j}(0 \leq i, j)\)：
\[a_{i,j} = \begin{cases} 1 & : j = 0 或 i = j\\ a_{i - 1, j} + a_{i - 1, j - 1} & : 0 < j < i\\ 0 & : j > i \end{cases} \]现在，\(Mr.Hu\) 站在 \((n, m)\) 这个位置，他想知道，他向上或向左上方 \(45\) 度望去，看到的数的和是多少。
从 \((n, m)\) 向上望去，他会看到 \((n, m), (n − 1, m), (n − 2, m), \dots,(0, m)\) 这些位置。
从 \((n, m)\) 向左上方 \(45\) 度望去，他会看到 \((n, m), (n − 1, m − 1), \dots\)，直到某一维的下标变为 \(0\)。
这个数可能很大，你只需将答案对 \(10^9 + 7\) 取模即可。
输入格式
第 \(1\) 行一个整数：\(T\)，表示数据组数。
接下来 \(T\) 行，每行格式为：dir n m，其中 \(dir\) 为 \(1\) 表示向上看，\(2\) 表示向左上方看，\((n, m)\) 为 \(Mr.Hu\) 现在的位置。
输出格式
对于每组数据，输出一行表示答案。
输入样例
2
1 3 2
2 3 2
输出样例
4
6
样例解释
表格左上角长成这样（行列都是从 \(0\) 开始的）：
\[1 \,\, 0 \,\, 0 \,\, 0\\ 1 \,\, 1 \,\, 0 \,\, 0\\ 1 \,\, 2 \,\, 1 \,\, 0\\ 1 \,\, 3 \,\, 3 \,\, 1 \]这样从 \((3, 2)\) 向上看，会看到：\(3, 1, 0, 0\)，和为 \(4\)。
向左上角看，会看到：\(3, 2, 1\)，和为 \(6\)。
数据规模
对于 \(30\%\) 数据，\(1 \leq n, m \leq 5000, 1 \leq T \leq 1000\)。
对于 \(100\%\) 数据，\(1 \leq n, m \leq 10^6, 1 \leq T \leq 50000\)。
T3
题目描述
\(Mr.Hu\) 觉得在学习过程中，需要举一反三，做一题要理解透，然后遇到相似的问题时能类似地转化。所以想了一道和以前类似的题目，相信聪明如你，肯定能轻而易举地解决。
\(Mr.Hu\) 会给你 \(n\) 个非负整数，然后从中选 \(k\) 个出来，然后把这 \(k\) 个数按位或起来，\(Mr.Hu\) 想知道有多少种选法，使得或起来的结果为 \(r\)。
输入格式
第 \(1\) 行一个整数 \(T\)，表示测试组数。
接下来 \(T\) 组数据，对于每组数据。
第 \(1\) 行两个整数 \(n, k, r\)。
接下来 \(1\) 行包含 \(n\) 个非负整数：\(a_1, a_2, \dots, a_n\)。
输出格式
对于每组数据，输出一行，包含一个整数，即方案数，因为结果可能很大，只需要对 \(10^9 + 7\) 取模即可。
输入样例
2
4 2 3
1 2 3 4
4 1 1
1 2 3 4
输出样例
3
1
样例解释
对于第一组数据，一共有 \(3\) 种选法：\((1, 2), (1, 3), (2, 3)\)。
对于第二组数据，一共有 \(1\) 种选法：\((1)\)。
数据规模
对于 \(10\%\) 数据，\(1 \leq n \leq 10, 0 \leq a_i < 2^{10}\)。
对于 \(30\%\) 数据，\(1 \leq n \leq 100, 0 \leq a_i < 2^{10}\)。
对于 \(50\%\) 数据，\(1 \leq n \leq 10^5, 0 \leq a_i < 2^{15}\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 10^5, 0 \leq a_i < 2^{20}, 1 \leq k \leq n, 1 \leq T \leq 5\)。
标签：opt,10,27,int,2024.9,校测,样例,leq,数据 From： https://www.cnblogs.com/JPGOJCZX/p/18436494