Preface
逆天PKU，出的什么寄吧东西，做题全靠打表找规律，一场比赛全是\(\bmod 998244353\)
4题成功从金到铜完美区分，我们队VP的时候两个半小时就下班了，看祁神写了3h的大几何题L
虽然徐神开场一眼看出了F是个诈骗题，但推了1h无果还是要上机打表找规律才发现式子
最后和徐神一起推K推出来一个复杂度看着就很假的容斥反演式子，后面一看题解妈的居然是能过的
这场因为好多题都不会就只写过了的题吧
C. Necklace
唯一一个看起来正常点的题目，YY了好多种贪心思路才过
首先最大值最小一眼二分答案，考虑怎么检验答案\(x\)是否合法
不妨假设覆盖的第一个关键点在覆盖其区间的右端点处，即我们尽可能给它留出更多向前的余量
对于接下来的每个区间，都贪心地让它们的右端点尽可能偏右，当然还要保证每个区间内只有一个关键点
考虑如果在某次操作中无法覆盖到某个关键点了，那么说明我们需要将前面所选的区间整体向右偏移一些，如果不能移动使得其能覆盖下个关键点，则直接返回无解
否则最后看看是否能把环覆盖完全即可，前面整体可以移动的偏移量可以一边扫一边算
最后不放心还换了个方向又算了一遍，今天又交了一遍发现只做一个方向也是对的
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5,INF=1e18;
#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(int &n){
for(n=0;(c=gc())<'0'||c>'9';);
for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
#undef gc
int n,m,a[N],b[N];
inline bool check(int *a,CI x)
{
int left=x-1,mi=left,pos=a[1]; for (RI i=2;i<=m;++i)
{
if (pos+x<a[i])
{
int shift=a[i]-pos-x; if (shift>mi) return 0;
left-=shift; mi-=shift; pos=a[i];
} else
{
mi=min(mi,a[i]-pos-1);
pos=min(pos+x,i!=m?a[i+1]-1:INF);
}
}
return pos-a[m]+left>=a[1]-1+n-a[m];
}
signed main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
RI i; for (read(n),read(m),i=1;i<=m;++i) read(a[i]),b[m-i+1]=n-a[i]+1;
int l=(n+m-1)/m,r=n,mid,ret; while (l<=r)
{
mid=l+(r-l)/2LL;
if (check(a,mid)||check(b,mid)) ret=mid,r=mid-1; else l=mid+1;
}
return printf("%lld",ret),0;
}
F. Cactus
本场最诈骗的一题，要勇敢跳出仙人掌计数的桎梏，发现只要\(f_i\)是两两不同的最后得到的结果都是相同的
VP时我们对由徐神上去写了个\(f_i=i,f_i=i^2,f_i=i^3\)后发现输出的都是斐波那契数列，然后交了一发就过了
证明的话可以去看Tutorial只能说是有点炸裂
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi mod = 998244353;
llsi ksm(llsi a, llsi b) {
llsi res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
inline llsi F(llsi n, llsi (*f)(llsi)) {
llsi res = 0;
for(int i = 1; i <= n; ++i) {
llsi pro = 1;
for(int j = 1; j <= n; ++j) if(j != i)
pro *= (1 + mod + f(i) - f(i) * f(j) % mod) % mod * ksm(f(i) - f(j) + mod, mod - 2) % mod,
pro %= mod;
res = (res + pro) % mod;
}
return res;
}
llsi f[3000005];
int main() {
int n; std::cin >> n;
f[1] = f[2] = 1;
for(int i = 3; i <= n; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
std::cout << f[n] << char(10);
return 0;
}
H. Three Integers
略微阳间的构造题，但就是这个签到难度的题搞了我快1h
考虑当\(a>c\)时，我们有如下构造法，令\(x=a\)，并选择一个最小的\(i\)使得\(ia+c>b\)，令\(z=ia+c\)
最后找一个最小的\(j\)使得\(jz+b>a\)，并令\(y=jz+b\)，手玩一下不难发现此时的\(x,y,z\)就是一组合法解
同理我们可以找出\(b>a\)以及\(c>b\)时的构造方法，此时可以覆盖所有三个数不完全相同的情况
考虑当\(a=b=c\)时，当且仅当\(a=b=c=0\)时有解，否则一定无解
#include<cstdio>
#include<iostream>
#include<assert.h>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,a,b,c;
signed main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld%lld",&a,&b,&c); int x,y,z,i,j;
if (a==b&&a==c&&b==c)
{
if (a==0) puts("YES\n1 1 1"); else puts("NO"); continue;
}
if (a>c) x=a,i=c>b?0:(b-c)/a+1,z=i*a+c,j=b>a?0:(a-b)/z+1,y=j*z+b;
else if (b>a) y=b,i=a>c?0:(c-a)/b+1,x=i*b+a,j=c>b?0:(b-c)/x+1,z=j*x+c;
else if (c>b) z=c,i=b>a?0:(a-b)/c+1,y=i*c+b,j=a>c?0:(c-a)/y+1,x=j*y+a;
printf("YES\n%lld %lld %lld\n",x,y,z);
//assert(x>0); assert(y>0); assert(y>0);
//assert(x%y==a); assert(y%z==b); assert(z%x==c);
}
return 0;
}
I. Pudding Store
妈的遇到计数题不会做怎么办，像这种输入一个数输出一个数的直接先打个表看看
然后这题规律也很简单，当\(n\le 3\)时答案就是\(n!\)；当\(n>3\)时答案就是\(2^{n-3}\times 6\)
当然具体的结论证明还是去看Tutorial吧，这题讲的还是挺详细的
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int mod=998244353;
int t,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;
}
int main()
{
//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
if (scanf("%d",&n),n==1) puts("1");
else if (n==2) puts("2"); else if (n==3) puts("6");
else printf("%d\n",6LL*quick_pow(2,n-3)%mod);
}
return 0;
}
K. Magus Night
好神的容斥反演题，感觉徐神昨天晚上推的东西和题解差不太多的说，但没想到复杂度这么炸裂的东西也能过
首先考虑对答案来个容斥，设\(T=\{\gcd(S)\le q\and \operatorname{lcm}(S)\ge p\}\)，即为我们所求的，同时我们定义：
则我们用不加任何限制的答案\((\sum_{i=1}^{m} i)^n\)，减去\(A+B\)就是最后要求的答案了
首先考虑\(A\)怎么算，这个是很经典的莫反，就是用\(\sum_{d|\gcd(i,j)} \mu(d)=[\gcd(i,j)=1]\)来替换\(\gcd\)的式子，得到：
然后就是计算\(B\)了，记\(f(j)\)表示\(\operatorname{lcm}(S)=j\)的贡献，但直接求不好求我们考虑用反演
记\(F(j)\)表示\(\operatorname{lcm}(S)|j\)的贡献，则\(F(j)=[\sigma(j)]^n\)，其中\(\sigma(j)\)表示\(j\)的约数和函数
同时根据定义，我们有\(F(j)=\sum_{d|j} f(d)\)，那么用一下反演的式子就得到\(f(j)=\sum_{d|j}\mu(d)\times [\sigma(\frac{j}{d})]^n\)
有了这个我们就可以计算\(B\)的值了，有：
然后直接对着最后那个式子算即可，复杂度上界是\(O(m\log m\log^2 p)\)的，但实际跑不满可以通过
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=998244353;
int n,m,p,q,pri[N],cnt,mu[N],sigma[N],vis[N]; vector <int> frac[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
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)
{
RI i,j; for (mu[1]=1,i=2;i<=n;++i)
{
if (!vis[i]) pri[++cnt]=i,mu[i]=-1;
for (j=1;j<=cnt&&i*pri[j]<=n;++j)
if (vis[i*pri[j]]=1,i%pri[j]) mu[i*pri[j]]=-mu[i]; else break;
}
for (i=1;i<=n;++i) for (j=i;j<=n;j+=i)
frac[j].push_back(i),inc(sigma[j],i);
}
int main()
{
//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
RI i,j,k; scanf("%d%d%d%d",&n,&m,&p,&q); init(m);
for (i=1;i<=m;++i) sigma[i]=quick_pow(sigma[i],n);
int ans1=quick_pow(1LL*m*(m+1)/2LL%mod,n);
int ans2=0; for (i=q+1;i<=m;++i)
{
int t=m/i; for (j=1;j<=t;++j)
inc(ans2,1LL*(mu[j]+mod)*quick_pow(1LL*(t/j)*(t/j+1)/2LL%mod*i%mod*j%mod,n)%mod);
}
int ans3=0; for (i=1;i<=q;++i)
{
int t=m/i; for (j=1;j<=t;++j)
{
int ret=0,lim=(p-1)/i/j;
for (k=1;k<=lim;++k) for (auto d:frac[k])
inc(ret,1LL*(mu[d]+mod)*sigma[k/d]%mod);
inc(ans3,1LL*(mu[j]+mod)*quick_pow(1LL*i*j%mod,n)%mod*ret%mod);
}
}
return printf("%d",(1LL*ans1-ans2-ans3+2LL*mod)%mod),0;
}
Postscript
珍爱生命，远离PKU.jpg