昨天考崩了QAQ

几乎写全了暴力分，然而并没有什么卵用

因为只要A掉一道题就比我分高了，比我分高的也至少A掉了一道题QAQ

感觉到一丝淡淡的忧桑

貌似THUSC最后听讲课的那些人几乎都A了两题

看来我的THUSC果然只是RP好啊

 

第一题

显然选色数最少的颜色，设颜色数为m

考虑存在某个点的方案数，设这个点到k距离i个点

则方案数为(n-1-i)！/ ((m-i)!*j!*k!……） j,k等是其他颜色的色数

总方案也是非常好算的，这样我们就可以计算每个点对于期望的贡献了

这样做是O(n^2)的

之后我们考虑t=1的暴力分

不难发现问题转化为维护等差数列的和

这是个分块的经典问题，当公差d>sqrt(n)的时候，暴力是sqrt(n)的

当d<sqrt(n)的时候我们可以预处理答案，每个修改的时候暴力把sqrt(n)个d都修改一遍

时间复杂度是O(n*sqrt(n))的

考试的时候只想到了这些，于是就只有50分

之后我们注意到当t>1的时候，m<=n/2

则一个点到k的距离每多一个点，概率至少/2

不难发现当我们距离很大的时候，概率很小对于本题的精度要求不会有影响，这样我们就不用计算了

然后t=1我们维护分块，t>1的时候我们暴力左右50-100个计算答案就可以了

QAQ 悲桑的事情是考后改题我就只给我的程序加了一句话，然后就A了 QAQ

总结一下为什么没有看出来每次概率要/2这件事情

因为我算的时候不是滚动过去算概率的QAQ我是取ln之后exp回去的

所以什么也看不出来

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std; const int oo=0x7fffffff;const int maxn=100010;int n,m,x,y,type,mn,blo;int t,k,d,c[maxn];int val[maxn];int S[330][330];long double jc[maxn]; void Get_pre(){ for(int i=1;i<=blo;++i){//步长 for(int j=1;j<=i;++j){ for(int k=j;k<=n;k+=i){ S[i][j]=S[i][j]+val[k]; } } } return;} int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)scanf("%d",&val[i]); jc[0]=0; for(int i=1;i<=n;++i)jc[i]=jc[i-1]+log(i); blo=(int)(sqrt(n)); Get_pre(); while(m--){ scanf("%d",&type); if(type==1){ scanf("%d%d",&x,&y); int v=y-val[x]; val[x]=y; for(int i=1;i<=blo;++i){ int Q=(x-1)%i+1; S[i][Q]+=v; } }else{ scanf("%d%d%d",&t,&k,&d); for(int i=1;i<=t;++i)scanf("%d",&c[i]); if(t==1){ int ans=0; if(d>blo){ ans=val[k]; for(int i=k+d;i<=n;i+=d)ans+=val[i]; for(int i=k-d;i>=1;i-=d)ans+=val[i]; }else{ int Q=(k-1)%d+1; ans=S[d][Q]; }printf("%d",ans); printf(".0000\n"); }else{ mn=oo;long double P=0; long double ans=0; for(int i=1;i<=t;++i){ mn=min(mn,c[i]); P=P-jc[c[i]]; } long double sum=P+jc[n-1]; int cnt=0;P=P+jc[mn]; for(int i=k+d;i<=n;i+=d){ cnt++; if(cnt>100)break; if(cnt>mn)break; long double tmp=P-jc[mn-cnt]+jc[n-1-cnt]-sum; ans=ans+exp(tmp)*val[i]; }cnt=0; for(int i=k-d;i>=1;i-=d){ cnt++; if(cnt>100)break; if(cnt>mn)break; long double tmp=P-jc[mn-cnt]+jc[n-1-cnt]-sum; ans=ans+exp(tmp)*val[i]; }ans=ans+val[k]; printf("%.4lf\n",(double)(ans)); } } }return 0;}
          
         
        
       
      
     

第二题

首先k=0是普及组的题目

k=1的时候求直径就可以了

k=n,c=1的时候问题中转换成了把这个树分割成最少的链

然后我就开始dp了，最后35分滚粗

考后跟lyc交流了一下发现我的dp做法只要加k一维多做个树上背包就能A了QAQ

我们知道k=n的时候是分割最少链

那么实际上这道题求的是把树分割成k条互不相交的链使得链上的边权和最大

不难发现这个问题具有可以dp的性质，做树上背包就可以了

转移的时候分类讨论一下QAQ

时间复杂度的分析同HAOI2015的那道一样，是O(nk)的QAQ

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int maxn=10010;const int oo=0x7fffffff/3;int n,K,c;int u,v,w,ans;int h[maxn],cnt=0;int sz[maxn];int f[2010][2010][2];int tmp[2010][2];struct edge{    int to,next,w;}G[maxn<<1]; void add(int x,int y,int z){    ++cnt;G[cnt].to=y;G[cnt].next=h[x];G[cnt].w=z;h[x]=cnt;}void read(int &num){    num=0;char ch=getchar();    while(ch<'!')ch=getchar();    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();}void DP(int u,int fa){    sz[u]=1;f[u][0][0]=0;f[u][1][1]=-c;    for(int k=h[u];k;k=G[k].next){        int v=G[k].to;        if(v==fa)continue;        DP(v,u);        for(int i=0;i<=sz[u]+sz[v];++i)tmp[i][0]=tmp[i][1]=-oo;        for(int i=0;i<=sz[u];++i){            for(int j=0;j<=sz[v];++j){                int now=i+j;                                 tmp[now][0]=max(tmp[now][0],f[u][i][0]+f[v][j][0]);                if(now>=1)tmp[now-1][0]=max(tmp[now-1][0],f[u][i][1]+f[v][j][1]+G[k].w+c);                                 tmp[now][1]=max(tmp[now][1],f[u][i][0]+f[v][j][1]+G[k].w);                tmp[now][1]=max(tmp[now][1],f[u][i][1]+f[v][j][0]);                         }        }sz[u]+=sz[v];        for(int i=0;i<=sz[u];++i){            f[u][i][0]=max(f[u][i][0],tmp[i][0]);            f[u][i][1]=max(f[u][i][1],tmp[i][1]);        }    }    return;} int main(){    while(scanf("%d%d%d",&n,&K,&c)==3){        memset(h,0,sizeof(h));cnt=0;ans=0;        for(int i=1;i
         
        
       
      
     

第三题

好神的题目！花了半天才弄懂

首先我们注意到如果我们给每个字母随机值之后计算行列式

不难发现如果行列式在模2意义下不为0，则一定是No，否则可能是Yes，也可能是No

然后某个奇怪的定理指出在域F下随机带入并计算行列式，行列式为0的概率是d/F

F是域的大小，这样我们只需要找到一个足够大的域F就可以了

显然不能是模2剩余系，因为大小为2

不妨构造一个系数均为0或1的k次多项式，我们让他对一个不可约多项式M取模，构成多项式环

域的大小显然是2^k

这样我们给每个字母随机一个多项式并计算行列式就可以了

由于是在模2意义下进行，所以多项式的运算可以采用位运算加速

设多项式f，g

则f-g=f+g=f^g

对于f*g我们可以采取类似快速乘的方式分解掉g并分别与f相乘

计算行列式的时候由于我们只关注是否为0，所以把除法转换成乘法

至于对M取模，即f=min(f,f-M)

即f=min(f,f^M)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int M=0x20000035; const int maxn=52;int T,n;int val[1010];int A[maxn][maxn];char s[maxn][maxn][112]; void read(char *s){    char c;    while(c=getchar(),c!='+'&&(c<'a'||c>'z')&&(c<'0'||c>'9'));    *(s++)=c;    while(c=getchar(),c=='+'||(c>='a'&&c<='z')||(c>='0'&&c<='9'))*(s++)=c;    *(s++)='+';*s=0;}int mul(int a,int b){    int s=0;    while(b){        if(b&1)s=s^a;        a<<=1;a=min(a,a^M);b>>=1;    }return s;}int Get_val(char *s){    int now=0,t=1,len=strlen(s);    for(int i=0;i
          
           ='a'&&s[i]<='z')t=mul(t,val[s[i]]); else t=s[i]-'0'; }return now;}bool Gauss(){ for(int i=1;i<=n;++i){ int k=0,to; for(to=i;to<=n;++to)if(A[to][i])break; if(to>n)return 1; if(to!=i)for(int j=1;j<=n;++j)swap(A[i][j],A[to][j]); for(int j=i+1;j<=n;++j){ if(A[j][i]){ int x=A[i][i],y=A[j][i]; for(int k=i;k<=n;++k){ A[j][k]=mul(A[j][k],x)^mul(A[i][k],y); } } } }return 0;}bool judge(){ for(int i='a';i<='z';++i)val[i]=rand(); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ A[i][j]=Get_val(s[i][j]); } }return Gauss();} int main(){ srand(809495818); scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)read(s[i][j]); bool flag=true; for(int T=10;T&&(flag=judge());T--); if(flag)printf("Yes\n"); else printf("No\n"); }return 0;}
          
         
        
       
      
     

考试的时候失误很大

首先第一题非常接近正解，然而没有注意到t>1的时候概率递减的非常快(因为我取得log之后exp回去的)

所以没有A掉

至于第二题已经成功把问题转化成分割链的问题了，而且知道了k没有限制时的DP做法

但是考试的时候没有继续思考，从而没有发现只要在加一维表示k就可以同样做DP了

第三题嘛QAQ