不知不觉就到了2018的最后一天。这个博客也有两个多月了。
我的姿势水平固然有了一定长进，但和巨神的距离却是越拉越远了。
这场CF也是，手速场我却没能有足够的手速。尤其是D题那种超简单的题目却死磕了半天才磕出来，F也没做出来。
总之，祝大家新年快乐_(:з」∠)_
CF1091A
依题意即可。
千万别掉进分类讨论的坑里。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int a,b,c;
void init(){
scanf("%d%d%d",&a,&b,&c);
--b,c-=2;
printf("%d",min(min(a,b),c)*3+3);
}
int main(){
init();
return 0;
}
CF1091B
我们将每个宝藏都加上每一个向量箭头，并标记目的地。
答案是任意一个被标记n次的。
可以用map或者hashmap维护。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int a[1005],b[1005],c[1005],d[1005];
typedef pair<int,int> pii;
typedef map<pii,int> mppii;
mppii mp;
int n;
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",a+i,b+i);
}
for(int i=1;i<=n;++i){
scanf("%d%d",c+i,d+i);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
pii nw(a[i]+c[j],b[i]+d[j]);
++mp[nw];
}
}
mppii::iterator it=mp.begin();
while(it!=mp.end()){
if(it->second==n){
printf("%d %d\n",it->first.first,it->first.second);
break;
}
++it;
}
}
int main(){
init();
return 0;
}CF1091C
观察题意以后我们发现，对于\(k\)，当且仅当\(n\%k == 0\)的时候，\(k\)会和其他的本质不同。
依据剩余系的性质容易证明。
那么我们就得到了一个朴素的求答案公式：
$$\forall x,st:n\% x==0,ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n+1) $$
然后考虑到\(n\%x==0\)，所以
$$ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n)==\sum_{i=0}^{n/gcd(n,x)-1}(1+ix)$$
套上等差数列求和公式即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline long long gcd(long long A,long long B){
return B?gcd(B,A%B):A;
}
long long n;
long long ans[100005],tp=0;
inline void calc(int X){
long long tms=n/gcd(n,X);
ans[++tp]=tms+((((tms*(tms-1))>>1)*X));
}
void init(){
scanf("%I64d",&n);
for(int i=1;i*i<=n;++i){
if(!(n%i)){
calc(i);
if(i*i!=n){
calc(n/i);
}
}
}
sort(ans+1,ans+1+tp);
tp=unique(ans+1,ans+1+tp)-1-ans;
for(int i=1;i<=tp;++i){
printf("%I64d ",ans[i]);
}
}
int main(){
init();
return 0;
}CF1091D
由于长度为\(n\)，显然序列的值必然是\(\frac{(n*(n+1))}{2}-SUM_i+SUM_{i+1}\), 其中\(SUM_{i}\)表示第\(i\)个排列的某个前缀和。
又排列的性质我们会发现，对于任意两个相邻的全排列，它的任意长度前缀和要么增加且前缀序列变化，要么前缀和保持不变且前缀序列保持不变。
故而，如果一个序列要满足要求，它只有两种情况——它本身就是一个排列，或者它横跨的两个排列必然有一部分前缀相同。
对于第一种情况我们可以看成它们的前缀有\(0\)个相同的。
问题转化为了，求所有排列中，两种相邻排列前缀相同的长度的和。
通过打表找规律，或者对全排列性质的精确推演，我们得到了这样一个求和式：
$$ ans=\sum_{pre=0}^{n-2}(n!-(\Pi_{i=n}^{n-pre+1}i))$$
但是暴力计算的复杂度最坏是\(n^2\)的，仍然无法通过此题。
我们考虑优化这个求和。优化的点在于\(\Pi_{i=n}^{n-pre+1}i\)，我们（毫不）惊讶地发现，它等价于\(\frac{n!}{n-pre}\)，所以我们可以预处理阶乘和阶乘的逆元。
这样就做完了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const long long MOD=998244353;
long long fac[1000005],inv[1000005];
long long n;
void init(){
scanf("%I64d",&n);
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%MOD;
inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
}
for(int i=2;i<=n;++i){
inv[i]=inv[i-1]*inv[i]%MOD;
}
long long ans=fac[n];
for(int i=1;i<=n-2;++i){
ans+=(fac[n]-fac[n]*inv[n-i]%MOD+MOD)%MOD;
ans%=MOD;
}
printf("%I64d",ans);
}
int main(){
init();
return 0;
}