暑假集训系列题解（十一）
题目1
题目链接
题目描述
image-20210822160147212样例输入
3
2 1
5 5
100 100样例输出
4
329462
294770659题解
将+和*分别转换为白球和黑球，将题目转换为n个不同的小球放到m个不同的盒子且不为空，即为第二类斯特林数，详见：https://github.tim-wcx.ltd/#/icpc/?id=组合数学，然后枚举白色小球盒子数目n，则对于黑色小球，有三种分法：n个盒子，n-1个盒子和n+1个盒子，对于三种情况分别计算求和即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll dp[4000][4000] = {0};
ll jc[4000] = {0};
int main()
{
jc[0] = 1;
for (ll i = 1; i < 4000; i++)
{
jc[i] = jc[i - 1] * i % mod;
}
dp[0][0] = 1;
for(int i=1; i<4000; i++)
{
for(int j=1; j<=i; j++)
{
dp[i][j] = ( dp[i-1][j-1] + (ll)j * dp[i-1][j] % mod ) % mod;
}
}
ll t;
scanf("%lld", &t);
while (t--)
{
ll n, m;
scanf("%lld%lld", &n, &m);
ll ans = 0;
for (ll i = 0; i <= max(n, m); i++)
{
ll tmp1 = dp[n][i] * jc[i];
tmp1 %= mod;
ans += tmp1 * dp[m][i - 1] % mod * jc[i - 1] % mod;
ans %= mod;
ans += tmp1 * dp[m][i] % mod * jc[i] % mod * 2 % mod;
ans %= mod;
ans += tmp1 * dp[m][i + 1] % mod * jc[i + 1] % mod;
ans %= mod;
}
printf("%lld\n", ans);
}
}题目2
题目链接
题目描述
骤风起，仓颉飘飘乎不自觉于孤岛焉。岛无人迹，唯有有理数二族尔。一族曰甲分之乙，
一族曰乙分之甲，甲、乙皆正整数。数之，则族族不竭其数。
鹦鹉谓仓颉：“日择二数，合其为平均或调和平均。造得一，吾送汝归！”
仓颉能归于九千九百九十九亿九千九百九十九万九千九百九十九日否？
仓颉被一阵风刮到了一个荒无人烟的小岛上，那里有两族有理数，ab和ba，（a,b 为正整数），每族数有无穷多个。
鹦鹉告诉仓颉：“每天，你可以选两个已有的数 x,y，将它们合成为$\frac{x+y}{2}$或$\frac{2x*y}{x+y}$。如果你能合成 1，我就送你回家！”
仓颉能在 999999999999 天内回家吗？
T 组数据。
输入
第一行一个正整数 T(1≤T≤400)，表示数据组数。
对于每组数据：
输入一行两个整数 a,b(1≤a,b≤$10^9$)，表示初始的有理数为$\frac{a}{b}$和$\frac{b}{a}$。
输出
对于每组数据：
输出一个字符串 “Yes” 或者 “No”（均不含引号），分别表示仓颉能或者不能在 999999999999 天内合成数字 1。
样例输入
3
1 1
1 2
5 3样例输出
Yes
No
Yes题解
规律题，由于a/b和b/a是任意多个的，可以多写几项找找规律。
代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf1 0x3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
map<ll,ll>mp;
int main()
{
ll sum=1;
for(ll i=1;i<=40;i++)
{
mp[sum]=1;
sum=sum*2;
}
ll t;
scanf("%lld",&t);
while(t--)
{
ll a,b;
scanf("%lld%lld",&a,&b);
ll tmp=__gcd(a,b);
a/=tmp,b/=tmp;
if(a==b)
{
puts("Yes");
continue;
}
if(mp[a+b]&&a%2==1&&b%2==1)
puts("Yes");
else
puts("No");
}
}题目3
题目链接
题目描述
Given is a sequence of N digits a1a2…aN, where each element is 1, 2, or 3. Let xi,j defined as follows:
$·x_{1,j}:=a_j (1≤j≤N)$
$·x_{i,j}:=|x_{i−1,j}−x_{i−1,j+1}| (2≤i≤N and 1≤j≤N+1−i)$
Find xN,1.
Constraints
·$2≤N≤10^6$
·ai=1,2,3 (1≤i≤N)
输入
Input is given from Standard Input in the following format:
N
a1a2…aN
输出
Print $x_{N,1}$.
样例输入
【样例1】
4
1231
【样例2】
10
2311312312样例输出
【样例1】
1
【样例2】
0提示
样例1解释
x1,1,x1,2,x1,3,x1,4 are respectively 1,2,3,1.
x2,1,x2,2,x2,3 are respectively |1−2|=1,|2−3|=1,|3−1|=2.
x3,1,x3,2 are respectively |1−1|=0,|1−2|=1.
Finally, x4,1=|0−1|=1, so the answer is 1.
题解
减法相当于模2加，将题目转变为
img即统计每一位数加了多少次，通过观察，每一位数加$C_{i-1}^{n-1}$，即判断奇偶即可。
参考博客：
https://blog.csdn.net/weixin_45750972/article/details/105271373
https://blog.csdn.net/weixin_45750972/article/details/105272194
https://www.cnblogs.com/Willems/p/12552885.html
代码
#include <bits/stdc++.h>
using namespace std;
int b[10] = {0};
char a[1005000] = {0};
int main()
{
int n;
scanf("%d", &n);
scanf("%s", a + 1);
int f1 = 0;
for (int i = 1; i <= n; i++)
{
a[i]--; ///由于n>=2，123等价于012计算
if (a[i] == '1')
f1 = 1;
b[a[i] - '0'] += (int)(((n - 1) & (i - 1)) == (i - 1));
}
if (b[1] & 1)
puts("1");
else if (f1 == 0 && (b[2] & 1))
puts("2");
else
puts("0");
}