Preface
这确实应该是我打过的比较水的CC了（其实就打过两场）
但由于我太弱了打的都是Div2，所以会认为上一场更简单，其实上一场Div的数据结构是真的毒
好了废话不多说快速地讲一下
A Easy Fibonacci
手玩一下那个删数的过程就是求一个最大的(2^kle n)，然后剩下的斐波那契数列某一位膜(10)可找循环节可矩乘
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=2,mod=10;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
struct Matrix
{
int mat[N][N],n,m;
inline Matrix(CI N=0,CI M=0)
{
n=N; m=M; memset(mat,0,sizeof(mat));
}
inline int* operator [] (CI x) { return mat[x]; }
friend inline Matrix operator * (Matrix A,Matrix B)
{
Matrix C(A.n,B.m); for (RI i=0;i<C.n;++i)
for (RI j=0;j<C.m;++j) for (RI k=0;k<A.m;++k)
inc(C[i][j],1LL*A[i][k]*B[k][j]%mod); return C;
}
friend inline Matrix operator ^ (Matrix A,long long p)
{
Matrix T(A.n,A.m); for (RI i=0;i<A.n;++i) T[i][i]=1;
for (;p;p>>=1,A=A*A) if (p&1) T=T*A; return T;
}
}; int t; long long n,p;
int main()
{
for (scanf("%d",&t);t;--t)
{
for (scanf("%lld",&n),p=1;(p<<1LL)<=n;p<<=1LL);
if (p==1) { puts("0"); continue; }
Matrix S(2,1),D(2,2); S[0][0]=D[0][0]=D[0][1]=D[1][0]=1;
S=(D^(p-2))*S; printf("%d
",S[0][0]);
}
return 0;
}
B Chef and Interesting Subsequences
原谅我的菜，刚开始看到这数据范围写了个meet in middle才发现跑不过
后来发现直接把数字排个序那么只有最大的那个可以随便取，组合数算一下即可
注意不要取膜！
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,k,a[N];
inline long long C(CI n,CI m,long long ret=1)
{
for (RI i=1;i<=n-m;++i) ret=ret*(m+i)/i; return ret;
}
int main()
{
//freopen("B.in","r",stdin);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]); sort(a+1,a+n+1); int lst=a[k],c1=0,c2=0;
for (i=1;i<=k;++i) if (a[i]==lst) ++c1;
for (i=1;i<=n;++i) if (a[i]==lst) ++c2;
printf("%lld
",C(c2,c1));
}
return 0;
}
C Chef Designed a Network
套路的分类讨论题，主要是注意小数据
我们发现最优连边方案一定是先连一条链，然后连接两端点的自环
接下来连接所有点的自环，然后连接两端点
注意了这点之后后面的就(n)个(n)个地一连即可
注意一下各种各样的细节
#include<cstdio>
using namespace std;
int t,n; long long m;
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d%lld",&n,&m);
if (n==1) { printf("%d
",m<=1?m:-1); continue; }
if (m<n-1||m>((1LL*n*(n-1)>>1LL)+n)) { puts("-1"); continue; }
if (n==2) { puts(m==1?"1":"2"); continue; }
if (m<=n+1) { puts("2"); continue; }
if (m<=(n<<1)) { puts("3"); continue; }
m-=(n<<1); if (n&1)
{
int ans=3,d=m/n; ans+=(d<<1); m-=1LL*n*d;
if (!m) { printf("%d
",ans); continue; }
if (m<=(n>>1)) printf("%d
",ans+1); else printf("%d
",ans+2);
} else printf("%d
",3+m/(n>>1)+(m%(n>>1)?1:0));
}
return 0;
}
D Chef and Good Subsequences
(le 8000)的质数很少，因此我们考虑直接把这个扔到状态里
但是还是不好处理，我们发现这是个子序列，那么意味着我排个序照样能做
那么就很简单了，我们选数的限制就是要求强制递增并且与上一个数不同，令(f_{i,j})表示选到(i)，上个结尾的质数排名是(j)的方案数
很容易发现对于不同的数字统计前缀和即可，复杂度(O(ncdot pi(8000)))
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=1e9+7;
int n,k,a[N],ct,ans,sum[N],f[N]; bool vis[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]),!vis[a[i]]&&(vis[a[i]]=1,++ct);
for (sort(a+1,a+n+1),k=ct<k?ct:k,ans=sum[0]=i=1;i<=n;++i)
{
for (j=1;j<=k;++j) inc(ans,sum[j-1]),inc(f[j],sum[j-1]);
if (a[i]!=a[i+1]) for (j=1;j<=k;++j) inc(sum[j],f[j]),f[j]=0;
}
return printf("%d",ans),0;
}
E Biladerim Icin
首先我们发现原式子等价于((a-1)cdot x^2+2bxy+(c-1)cdot y^2)必有(a>1,c>1)，因此把(a,c)减去(1)同时变为(ax^2+2bxy+cy^2)
考虑配方法，上面的式子等价于((sqrt acdot x+frac{b}{sqrt a}cdot y)^2+(c-frac{b^2}{a})cdot y^2>0)
由于前面的一项必定不为(0)那么只要(c-frac{b^2}{a}>0)即(ac>b^2)即可
刚开始我naive地准备除法分块，但是蓝指导指导我只要分类讨论一下即可
考虑(ac>b^2)只有以下两种情况：(a>b)且(c>b)或(a,c)中一个(>b)，另一个(le b)
前面的直接算一下就好了，后面的枚举其中一个(le b)的，然后直接除过去看下另外一边的范围即可
复杂度(O(b^2))，代码十分好写
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int mod=1e9+7;
int t,a,b,c,ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d%d",&a,&b,&c); --a; --c; ans=0;
for (RI i=1,j;i<=b;++i)
{
inc(ans,1LL*max(a-i,0)*max(c-i,0)%mod);
for (j=min(i,a);j;--j) inc(ans,max(c-i*i/j,0));
for (j=min(i,c);j;--j) inc(ans,max(a-i*i/j,0));
}
printf("%d
",ans);
}
return 0;
}
F Fuzzy Linear Combinations
首先那个奇怪的方程只要用裴蜀定理转化一下就变成统一区间(gcd)为某值的题目了
刚开始我想了一个分治+二分的做法，基于(gcd)的变化是(log)级别的可以做到(O(nlog^3 n))的复杂度（主要算(gcd)要(log)）
后来一想既然都是(log)级别的了直接统计出以每一个点位右端点是所有后缀的答案，直接转移即可，复杂度就是(O(nlog^2 n))的
以下代码是脑抽了写出来的，手动实现了一个类似map的东西，建议大家用map
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,LIM=1e6;
//int mx;
struct data
{
int v[N],num[N],cnt,rst[N],tp[N];
inline void insert(CI x,CI y)
{
v[++cnt]=x; num[cnt]=y;
}
inline void reunoin(void)
{
//mx=max(mx,cnt);
RI i,j; for (i=1;i<cnt;++i) for (j=i+1;j<=cnt;++j)
if (v[i]>v[j]) swap(v[i],v[j]),swap(num[i],num[j]);
for (i=1;i<=cnt;++i) rst[i]=v[i]; int nc=unique(rst+1,rst+cnt+1)-rst-1;
for (i=1;i<=nc;++i) tp[i]=0; for (i=1;i<=cnt;++i)
tp[lower_bound(rst+1,rst+nc+1,v[i])-rst]+=num[i];
for (i=1;i<=nc;++i) v[i]=rst[i],num[i]=tp[i]; cnt=nc;
}
}lst,nw; int n,q,k,a[N],x; long long bkt[LIM+5];
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
int main()
{
//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (lst.insert(a[1],1),(a[1]<=LIM&&(bkt[a[1]]=1)),i=2;i<=n;++i)
{
for (nw.insert(a[i],1),j=1;j<=lst.cnt;++j)
nw.insert(gcd(lst.v[j],a[i]),lst.num[j]);
for (j=1;j<=nw.cnt;++j) if (nw.v[j]<=LIM) bkt[nw.v[j]]+=nw.num[j];
for (nw.reunoin(),j=1;j<=nw.cnt;++j) lst.v[j]=nw.v[j],lst.num[j]=nw.num[j];
for (lst.cnt=nw.cnt,j=1;j<=nw.cnt;++j) nw.v[j]=nw.num[j]=0; nw.cnt=0;
}
//for (i=1;i<=10;++i) printf("%d ",bkt[i]); putchar('
');
//printf("%d
",mx);
for (scanf("%d",&q),i=1;i<=q;++i)
{
long long ans=0; for (scanf("%d",&x),j=1;j*j<=x;++j)
if (x%j==0) ans+=bkt[j]+(x/j!=j?bkt[x/j]:0); printf("%lld
",ans);
}
return 0;
}
G Doofish Set
本场比赛唯一需要思考的一道题目，还是卡了一下的
首先我们发现有个完全图的部分分，考虑下怎么做
很容易想到分治或者二进制分组的做法，二进制分组的话就是用(log)级别的操作来使得每两个数必然有至少一次被分在不同的集合里
那么做法也出来了，不是完全图的话我们就每次把它补图的最大团找出来缩起来，然后看下缩完的图是不是完全图，是的话在继续套用上面的方法即可
是不是很简单，注意一下各种奇怪的细节
#include<cstdio>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
struct edge
{
int to,nxt;
}e[N<<2]; int head[N],n,m,x,y,cnt,bel[N],deg[N],ct[N],tot,lim; set <int> s; bool vis[N];
inline void addedge(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt; ++deg[x];
e[++cnt]=(edge){x,head[y]}; head[y]=cnt; ++deg[y];
}
int main()
{
//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d",&x,&y),addedge(x,y); for (i=1;i<=n;++i) s.insert(i);
for (i=1;i<=n;++i) if (!bel[i])
{
if (s.count(i)) s.erase(i); for (ct[bel[i]=++tot]=1,j=head[i];j;j=e[j].nxt)
if (!bel[e[j].to]&&s.count(e[j].to)) s.erase(e[j].to),vis[e[j].to]=1;
for (set <int>::iterator it=s.begin();it!=s.end();++it) ++ct[tot],bel[*it]=tot;
for (s.clear(),j=head[i];j;j=e[j].nxt)
if (vis[e[j].to]) s.insert(e[j].to),vis[e[j].to]=0;
}
for (i=1;i<=n;++i)
{
if (deg[i]!=n-ct[bel[i]]) return puts("-1"),0;
for (j=head[i];j;j=e[j].nxt) if (bel[e[j].to]==bel[i]) return puts("-1"),0;
}
if (!m) return puts("0"),0; for (lim=1;(1<<lim)<tot;++lim);
if (lim*n>1000000) return puts("-1"),0;
for (printf("%d
",lim),i=0;i<lim;++i,putchar('
'))
for (j=1;j<=n;++j) printf("%d",(bel[j]-1>>i)&1);
return 0;
}
Postscript
最后还是涨了两百多分，终于脱离了Div2的魔爪了233
话说为什么这么多人去打Challenge了啊，害的这场排名比上一次低了好多
总而言之我还是太菜了