Preface
在寝室白兰了一周多后也是终于等到徐神归来开始训练了
这场的题感觉比较偏数学了，感觉和之前打的一个 Tokyo 的 Open Cup 很像，因此后期挺坐牢的
4h 左右堪堪写出 7 题，最后全队 Rush D 结果发现暴力打表都打错了，怎么回事呢
A. Square Sum
这题在 去年暑假前集训数学专题 中做过类似的版本，只不过那个题的模数是没有平方质因子的奇质数
这题思路应该也是类似，但需要对 \(2\) 的情况进行一些讨论，代码先坑着有空来补
B. Super Meat Bros
题都没看，鉴定为不可做
C. Testing Subjects Usually Die
题都没看，鉴定为不可做
D. Triterminant
感觉思路没啥问题，就是三步走：解行列式——找合法序列的充要条件——计算最小操作次数
第一步就是线代课后习题的难度，不过推出式子后得到的结论很神秘，然后跑了个暴力打表发现并没有找到什么规律
后面看了 WIFI 的代码发现似乎是暴力写挂了（或者是前面搞错了），需要再反思下
E. Garbage Disposal
分类讨论题，首先特判掉 \(L=R\) 的情况
考虑若 \([L,R]\) 中有偶数个数，显然让相邻两个数两两配对一定合法
否则若 \([L,R]\) 中有奇数个数，若此时 \(L\) 为奇数，则可以让前 \(3\) 个数按：\((L,L+1),(L+1,L+2),(L+2,L)\) 的方式来配对
因为 \((L+2,L)\) 一定互质，而其余两组都是相邻的数因此也必然互质；剩下后面的偶数个数还是类似地两两配对即可
否则当 \(L\) 为偶数时一定无解，因为根据鸽笼原理，必然会有至少一对偶数要配对，显然无解
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,L,R;
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&L,&R);
if (L==R)
{
puts(L==1?"1":"-1"); continue;
}
if ((R-L+1)%2==0)
{
for (RI i=L;i+1<=R;i+=2)
printf("%d %d ",i+1,i); putchar('\n');
} else
{
if (L%2==0) { puts("-1"); continue; }
printf("%d %d %d ",L+1,L+2,L);
for (RI i=L+3;i+1<=R;i+=2)
printf("%d %d ",i+1,i); putchar('\n');
}
}
return 0;
}
F. Palindromic Polynomial
题都没看，鉴定为不可做
G. Palindromic Differences
徐神开场写的，我题目都没看
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi mod = 1'000'000'009;
constexpr llsi $n = 500005;
constexpr llsi ksm(llsi a, llsi b) {
llsi r = 1;
while(b) {
if(b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
return r;
}
llsi fac[$n], facinv[$n], p2[$n];
void prep(int n) {
fac[0] = 1; p2[0] = 1;
for(int i = 1; i <= n; ++i) p2[i] = p2[i - 1] * 2 % mod;
for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
facinv[n] = ksm(fac[n], mod - 2);
for(int i = n; i >= 1; --i) facinv[i - 1] = facinv[i] * i % mod;
return ;
}
int n, a[$n];
void work() {
std::cin >> n;
for(int i = 1; i <= n; ++i) std::cin >> a[i];
std::sort(a + 1, a + n + 1);
llsi ans = fac[n / 2];
int cnt = 1;
for(int i = 2, j = n - 1; ; ++i, --j) {
if(a[i] + a[j] != a[i - 1] + a[j + 1]) {
ans = 0;
break;
}
if(i < j && a[i] == a[i - 1]) cnt++;
else {
ans = ans * facinv[cnt] % mod;
if(a[i - 1] != a[j + 1]) ans = ans * p2[cnt] % mod;
cnt = 1;
}
if(i >= j) break;
}
if((n & 1) && a[n / 2 + 1] * 2 != a[1] + a[n]) ans = 0;
std::cout << ans << char(10);
// if(n == 14) std::cout << fac[7] * p2[7] % mod << char(10);
return ;
}
int main() {
std::ios::sync_with_stdio(false);
prep(500000);
int T; std::cin >> T; while(T--) work();
return 0;
}
H. Graph Isomorphism
神秘分类讨论题
注意到和一个图同构的图数量在没什么特殊限制时大概率是 \(n!\) 级别的，因此当 \(n\) 足够大时绝大多数图都是无解的
手玩一波会发现菊花图因为有一个 fixed point 的存在，因此恰好有 \(n\) 种同构图
与此同时比较隐蔽的还有菊花图的补图，即一个孤点加上一个完全图也是合法的
另外还有些特殊情况，例如点数小于等于 \(3\) 的图、完全图，最坑的是当 \(n=4\) 时四元环和每个点度数为 \(1\) 的图也是有解的
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,m,x,y,deg[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m);
for (RI i=1;i<=n;++i) deg[i]=0;
for (RI i=1;i<=m;++i)
scanf("%d%d",&x,&y),++deg[x],++deg[y];
if (n<=3) { puts("YES"); continue; }
if (n==4&&m==2&°[1]==1&°[2]==1&°[3]==1&°[4]==1) { puts("YES"); continue; }
if (n==4&&m==4&°[1]==2&°[2]==2&°[3]==2&°[4]==2) { puts("YES"); continue; }
if (m==1LL*n*(n-1)/2) { puts("YES"); continue; }
int center=0,outer=0;
for (RI i=1;i<=n;++i)
if (deg[i]==n-1) ++center; else if (deg[i]==1) ++outer;
if (center==1&&outer==n-1) { puts("YES"); continue; }
int iso=0,kernel=0;
for (RI i=1;i<=n;++i)
if (deg[i]==0) ++iso; else if (deg[i]==n-2) ++kernel;
if (iso==1&&kernel==n-1) { puts("YES"); continue; }
puts("NO");
}
return 0;
}
I. DAG Generation
不会 Counting 怎么办，我们只需要暴力打表并找规律即可轻松过题
首先计算相同的概率显然更简单，同时不妨把生成图的方式稍作变换，先随机固定一个排列，然后钦定边只能从前面的点连向后面的点，不难发现这种生产方式和原题的表述等价
考虑总的方案数作为分母是 \([n!\times 2^{\frac{n(n-1)}{2}}]^2\)，现在我们要对每一种具体的方案去重后平方累计贡献得到分子
写一个暴力会发现分子形如 \(n!\times (2^1-1)\times (2^2-1)\times (2^n-1)\)，因此最后答案的表达式即为：
\[1-\frac{(2^1-1)\times (2^2-1)\times (2^n-1)}{n!\times 2^{n(n-1)}} \]#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi mod = 1'000'000'009;
constexpr llsi $n = 500005;
constexpr llsi ksm(llsi a, llsi b) {
llsi r = 1;
while(b) {
if(b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
return r;
}
llsi fac[$n], facinv[$n], p2[$n], hkr[$n];
void prep(int n) {
fac[0] = 1; p2[0] = 1; hkr[0] = 1;
for(int i = 1; i <= n; ++i) p2[i] = p2[i - 1] * 2 % mod;
for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
facinv[n] = ksm(fac[n], mod - 2);
for(int i = n; i >= 1; --i) facinv[i - 1] = facinv[i] * i % mod;
return ;
}
int main() {
std::ios::sync_with_stdio(false);
prep(100000);
hkr[1] = 1;
for(int i = 2; i <= 100000; ++i) hkr[i] = hkr[i - 1] * (p2[i] - 1) % mod;
int T; std::cin >> T; while(T--) {
llsi n; std::cin >> n;
llsi ans = hkr[n] * fac[n] % mod;
ans = ans * ksm(fac[n] * ksm(2, n * (n - 1) / 2) % mod, (mod - 2) * 2) % mod;
std::cout << (1 + mod - ans) % mod << char(10);
}
}
J. Persian Casino
小清新 Counting 题，想清楚策略后就很简单了
注意到最优策略一定是先一直做，直到 rollback 的次数全部耗尽；接下来的部分怎么操作都不会改变答案的期望了
因此最坏情况下，若 \(2^m<n-m\)，即前 \(m\) 轮就用完了 rollback，此时积攒的钱不够后面每轮投一块钱，此时无解
否则必然有解，考虑计算期望，不难发现最后的钱数只和倍增的轮次有关，不妨枚举最后恰好倍增了 \(k\) 次
分情况讨论，当 \(k<n\) 时，这种情形的概率为 \(C_{m-1}^{k-1}\times \frac{1}{2^k}\)，钱数为 \(2^k\)，因此总贡献为 \(\sum_{k=m}^{n-1} C_{m-1}^{k-1}=C_n^m\)
当 \(k=n\) 时，改为枚举一共用了多少次 rollback，总贡献为 \(\sum_{i=0}^{m-1} C_n^i\times \frac{1}{2^n}\times 2^n=\sum_{i=0}^{m-1} C_n^i\)
因此最后合并一下发现答案就是 \(\sum_{i=0}^{m} C_n^i\)，计算十分容易
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=1e9+9;
int t,n,m,fact[N],ifac[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
fact[0]=1; for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
ifac[n]=quick_pow(fact[n]); for (RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
if (n<0||m<0||n<m) return 0;
return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
for (scanf("%d",&t),init(1e5);t;--t)
{
scanf("%d%d",&n,&m);
if (m<=20&&(1<<m)<n-m) { puts("bankrupt"); continue; }
int ans=0; for (RI i=0;i<=m;++i) (ans+=C(n,i))%=mod;
printf("%d\n",ans);
}
return 0;
}
K. Determinant, or...?
计算行列式的值的经典思路就是转为上/下三角矩阵后把对角线乘起来，因此考虑消元
不难发现原矩阵可以等分为四个部分，其中除左上角区域外的三个部分内的数完全相同
考虑把矩阵的上半部分减去下半部分，这样就可以把右上角部分全部变为 \(0\)
而左上角部分不难发现扔满足上述性质，递归处理即可将整个行列式变为下三角矩阵，总复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
constexpr int mod = 1'000'000'009;
int a[1 << 20];
int64_t calc(int l, int r) {
if(r == l + 1) return a[l];
int mid = (l + r) >> 1;
for(int i = l; i < mid; ++i) a[i] = (a[i] + mod - a[i + r - mid]) % mod;
return calc(l, mid) * calc(mid, r) % mod;
}
int main() {
std::ios::sync_with_stdio(false);
int n; std::cin >> n; n = 1 << n;
for(int i = 0; i < n; ++i) std::cin >> a[i];
std::cout << calc(0, n) << char(10);
return 0;
}
L. Directed Vertex Cacti
题都没看，鉴定为不可做
M. Siteswap
祁神 solo 的一个神秘模拟题（？），我连题意都看不懂，好像细节挺多很容易写挂
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n, A[N];
bool vis[N];
void solve(){
cin >> n;
for (int i=0; i<n; ++i) cin >> A[i], vis[i]=false;
int ans[3] = {0, 0, 0};
for (int i=0; i<n; ++i) if (!vis[i]){
if (0==A[i]){
vis[i]=true;
continue;
}
if (A[i]%n==0){
int res = A[i]/n;
if (n%2==0) ans[i%2] += res;
else{
if (res%2==0){
ans[i%2] += (res+1)/2;
ans[(i+1)%2] += res/2;
}else ans[2] += res;
}
continue;
}
int loops = 0;
bool odd = false;
int cur = i;
while (!vis[cur]){
int res = (cur+A[cur])/n;
loops += res;
if (A[cur]%2==1) odd=true;
vis[cur]=true;
cur = (cur+A[cur])%n;
}
if (!odd){
// printf("n%2=%lld\n", n %2);
if (n%2==0) ans[i%2] += loops;
else{
if (loops%2==0){
ans[i%2] += (loops+1)/2;
ans[(i+1)%2] += loops/2;
}else ans[2] += loops;
}
}else ans[2] += loops;
}
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
Postscript
感觉这场题都不太对我们队的好球区啊，这斯拉夫人怎么和日本人一样喜欢出一堆数学题呢
标签：std,Cup,int,Zaporizhzhia,Universal,llsi,ans,include,mod From： https://www.cnblogs.com/cjjsb/p/18387457