Preface
最近可能中了降智病毒，写什么都写不过
下午打的校趣味赛看错题一个爆搜WA了四次，少罚一次时都Rank1了
然后晚上CF先是C想半天，然后D作为曾经最擅长的计数题也漏想了一种状态可能性，对着\(O(n)\)的假复杂度算法看半天
懂不懂什么叫六连掉的含金量啊，不过值得一提的是今天找到了一个以前WC拿Ag的爷预组队，我已经准备好被带飞了
A. Doremy's Paint
SB题，不难发现区间往外扩展一定不会让答案变劣，因此直接输出1 n即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
printf("1 %d\n",n);
}
return 0;
}
B. Doremy's Perfect Math Class
不难发现辗转相减的过程得到的数不会小于所有数的\(\gcd\)，设为\(g\)
因此\(g\)一定是最小的划分单位，能表出的数一定是\(g\)的倍数，故答案就是\(\frac{a_n}{g}\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],g;
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (g=a[1],i=2;i<=n;++i) g=gcd(g,a[i]);
printf("%d\n",a[n]/g);
}
return 0;
}
C. Doremy's City Construction
刚开始其实早就想到构造方法了，不过被相等的中间段搞了，跌跌撞撞才过
首先假设所有数都不相同，则我们可以把所有数排序后，选一个断点把所有数分成两个集合
不难发现只要两个集合之间相互连边一定是满足题意的，故偶数时答案最大为\((\frac{n}{2})^2\)，奇数时最大为\((\frac{n-1}{2}\times \frac{n+1}{2})\)
考虑如果存在相同的数，我们就不能粗暴地在中间位置进行划分了，因为如果相同的数被分在了两个集合里就一定不合法
那么我们发现所有的合法端点就是每一段数的分界点，直接枚举取最大的一个即可
注意特判所有数都相同的情况，答案为\(\lfloor\frac{n}{2}\rfloor\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
long long ans=0; for (sort(a+1,a+n+1),i=1;i<n;++i)
if (a[i]!=a[i+1]) ans=max(ans,1LL*i*(n-i));
printf("%lld\n",max(ans,1LL*n/2));
}
return 0;
}
D. Doremy's Pegging Game
首先我们要转化出一个碰到蓝点的充要条件，设\(t=\lfloor\frac{n}{2}\rfloor\)
则当局面中第一次出现大于等于\(t\)个被移除的红点时则碰到了蓝点
刚开始我就naive地认为停止的局面一定是恰好有\(t\)个被移除的红点，因此一直卡着
那么我们考虑枚举停止时被移除的红点的个数\(i(t\le i\le n-2+[n\text{ is even}])\)
我们发现此时两个端点是不能被移除的，还剩下另一侧有\(n-2-i\)个点，枚举其中事前被移除的点个数\(j\)
考虑最后一次移除一定造就了连续\(i\)个被移除点的局面，因此方案数为\(2t-i\)，然后乘上另一边选要删除的点的方案数\(C_{n-2+[n\text{ is even}]}^{j}\)
由于前\(i+j-1\)个点的顺序不变要乘上\((i+j-1)!\)，且最后要记得乘上环上选起始位置的方案数\(n\)
把具体式子写一起就是：
\[\begin{aligned} & n\times \sum_{i=t}^{n-2+[n\text{ is even}]} \sum_{j=0}^{n-2-i}C_{n-2+[n\text{ is even}]}^{j}\times (i+j-1)!\times(2t-i) \end{aligned} \]复杂度\(O(n^2)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
int n,mod,fac[N],ifac[N],pw[N],ans;
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 int C(CI n,CI m)
{
if (n<0||m<0||m>n) return 0;
return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline void init(CI n)
{
RI i; for (fac[0]=i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
for (ifac[n]=quick_pow(fac[n]),i=n-1;~i;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
for (pw[0]=i=1;i<=n;++i) pw[i]=pw[i-1],inc(pw[i],pw[i-1]);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&mod),init(n),i=n/2;i<=n-2;++i)
for (j=0;j<=n-i-2;++j) inc(ans,1LL*C(n-i-2,j)*(n/2*2-i)%mod*fac[i+j-1]%mod);
if (!(n&1)) inc(ans,fac[n-2]); return printf("%d",1LL*ans*n%mod),0;
}