前言

这场比赛做的很失败,虽然出题人背了大锅,但是毕竟最后打铁的还是自己,好在自己只是 VP 了失败了快感,并没有真正的霸占学校 CCPC\text{CCPC} 名额坐牢

I

题目大意,询问长度为 nn 的全排列 PP ,有多少满足对于每一个 i[1,n]i \in [1,n] , PP 的前 ii 个数前缀和满足 i2Sni | 2*S_n

考场上面打表做的,具体就是发现从 33 开始,方案数都是前面的两倍。

关于证明,我想的是 Sn=n(n+1)2S_n=\frac{n*(n+1)}{2}

我们可以通过把 n+1n+1 换进来,把 11 放在最后,实现前缀和变为 n(n+3)2\frac{n*(n+3)}{2} 依然可以被 ii 整除

那为什么不能和 3,5,73,5,7 这些交换呢?此时 SS 的表达式出现了丑陋的常数,消不掉,但是在 n3n\leq3 时候,常数不重要,因为手推发现能够除

H

坐大牢,三个人调试一摩尔时间,坐大牢。

给你三个数字 a,b,ca,b,c 满足

xmody=aymodz=bzmodx=cx\mod y=a\\y\mod z=b\\z\mod x=c

让你求满足条件的 x,y,zx,y,z 任取一个即可。

刚开始的想法是构造出来形如 (a,a+b+c,a+c)(a,a+b+c,a+c) (假设aa 最大)

并且推出来一个性质, a,b,ca,b,c 一定有一个数字是原数,我们不妨令最大的那个就是,比如当前我们令 aa 最大,一定有 x=ax=a ,但是我的构造一直没想出来,我们转而一想

x=k1y+ay=k2z+bz=k3x+cx=k_1y+a\\y=k_2z+b\\z=k_3x+c

有这个条件,我们在令 x=ax=a ,并,一定有 z>bz>bk3x+c>bk_3x+c>b 可以把 zz 求出来,再有 y>ay>abb 求出来。

其实只要xx 不是最小数就可以,因为最大和次大都可能是原数,但是最小的绝对不可能,因为模这个会得到更小的。

并且用这个方式的话,我们不需要考虑 00 的情况,我的构造方式可能以后会补上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
signed main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>a>>b>>c;
if (a == b && b == c)
{
if (a == 0) cout << "YES" << endl << "1 1 1" << endl;
else cout << "NO" << endl;
continue;
}
if(a>c)
{
x = a;
z = max((b - c) / x+1, 1ll) * x + c;
y = max((a - b) / z+1, 1ll) * z + b;
}
else if(b>a)
{
y = b;
x = max((c - a) / y+1, 1ll) * y + a;
z = max((b - c) / x+1, 1ll) * x + c;
}
else if(c>b)
{
z = c;
y = max((a - b) / z+1, 1ll) * z + b;
x = max((c - a) / y+1, 1ll) * y + a;
}
cout << "YES" << endl;
cout << x << " " << y << " " << z << endl;
}
}