骗分过样例,暴力出奇迹

2017年上海市计算数学代表队选拔赛

Overview

一题贪心,一题树形动态规划,一题网络流,三题数学。

其实都是正解远简单于骗分系列的题目。

题意设计的比较难懂,而且正解虽然都很"初等",但是都不太好想。很容易就会想到大方向,但要推出需要深厚的数学功底。

Task 1 exam 期末考试

问题描述

nn 位同学,每位同学都参加了全部的 mm 门课程的期末考试,都在焦急的等待成绩的公布。

ii 位同学希望在第 tit_i 天或之前得知所有课程的成绩。如果在第 tit_i 天,有至少一门课程的成绩没有公布,他就会等待最后公布成绩的课程公布成绩,每等待一天就会产生 CC 不愉快度。

对于第 ii 门课程,按照原本的计划,会在第 bib_i 天公布成绩。

有如下两种操作可以调整公布成绩的时间:

  1. 将负责课程 XX 的部分老师调整到课程 YY,调整之后公布课程X成绩的时间推迟一天,公布课程 YY 成绩的时间提前一天;每次操作产生 AA 不愉快度。
  2. 增加一部分老师负责学科 ZZ,这将导致学科 ZZ 的出成绩时间提前一天;每次操作产生 BB 不愉快度。

上面两种操作中的参数 X,Y,ZX,Y,Z 均可任意指定,每种操作均可以执行多次,每次执行时都可以重新指定参数。

现在希望你通过合理的操作,使得最后总的不愉快度之和最小,输出最小的不愉快度之和即可。

输入格式

第一行三个非负整数 A,B,CA,B,C ,描述三种不愉快度,详见问题描述;

第二行两个正整数 n,m(1 n,m 105)n,m(1\le\ n,m\leq\ 10^5) ,分别表示学生的数量和课程的数量;

第三行 nn 个正整数 tit_i ,表示每个学生希望的公布成绩的时间;

第四行 mm 个正整数 bib_i ,表示按照原本的计划,每门课程公布成绩的时间。

输出格式

输出一行一个整数,表示最小的不愉快度之和。

数据范围和约定

解法

看上去这题就是可贪的。所有的骗分解法实质上都是这题的正解的特例。在假设 n,m,ti,bin,m,t_i,b_i 同阶的前提下,有两种可以通过的做法:

  1. O(NlogN)O(N log N) ,考虑最晚出成绩的时间和代价之间的关系,数学推证出两者之间的函数是单峰函数。那么对这个函数作三分,找这个函数的最小值。在计算这个函数的时候,如果 BBAA 小,那么全部提前,否则尽量挪动,到剩下的无法挪动后将其提前。

    #include <stdio.h> 
    #include <ctype.h> 
    #define MAXN 100000+20 
    #define MAXM 100000+20 
    #define max(a,b) ((a)>(b)?a:b) 
    #define min(a,b) ((a)<(b)?a:b) 
    long long T[MAXN],B[MAXM],a,b,c,latest; 
    int N,M; 
    long long in(){ 
         long long ret=0;char ch=getchar(); 
         while(!isdigit(ch)) ch=getchar(); 
         while(isdigit(ch)) { 
                            ret=ret*10+ch-'0'; 
                            ch=getchar(); 
                            } 
         return ret; 
    } 
    long long cost(long long time){ 
        long long ret=0; 
        for(int i=1;i<=N;++i) if(T[i]<time) ret+=c*(time-T[i]); 
        if(a<b){ 
            long long more=0,less=0; 
            for(int i=1;i<=M;++i){ 
                    if(B[i]>time) more+=B[i]-time; 
                    if(B[i]<time) less+=time-B[i]; 
            } 
            if(more<=less) ret+=more*a; 
            else ret+=less*a+(more-less)*b; 
        } 
        else for(int i=1;i<=M;++i) if(B[i]>time) ret+=(B[i]-time)*b; 
        return ret; 
    } 
    int main(){ 
        a=in(),b=in(),c=in(); 
        scanf("%d%d",&N,&M); 
        for(int i=1;i<=N;++i) T[i]=in(); 
        for(int i=1;i<=M;++i) { 
            B[i]=in(); 
            latest=max(latest,B[i]); 
        } 
        long long L=1,R=latest+1,tag1,tag2,Ans=1e18; 
        while(R-L+1>=10){ 
            tag1=L+(R-L)/3,tag2=L+2*(R-L)/3; 
            if(cost(tag1)<=cost(tag2)) R=tag2; 
            else L=tag1; 
        } 
        for(register long long i=L;i<=R;++i) Ans=min(Ans,cost(i)); 
        printf("%lld\n",Ans); 
    } 
    

  2. O(N)O(N) ,对原始时间和学生排序 ,维护有多少个课程原始时间比当前的时间早,并维护比当前时间早或晚的总天数。那么枚举新的时间,考虑有多少课程从比它早变为比它晚。增量式的计算代价即可。用计数排序可以做到线性复杂度。

    #include<iostream>
    #include<cstdio>
    #include <ctype.h>
    #include<cstdlib>
    #include<cstring>
    #define MAXN 100005
    #define INF 1e16
    typedef long long LL;
    using namespace std;
    int n,m,a,b,c,t;
    LL student[MAXN],course[MAXN];
    long long read(){ 
         long long ret=0;char ch=getchar(); 
         while(!isdigit(ch)) ch=getchar(); 
         while(isdigit(ch)) { 
                            ret=ret*10+ch-'0'; 
                            ch=getchar(); 
                            } 
         return ret; 
    } 
    int main()
    {
        a=read(),b=read(),c=read(),n=read(),m=read();
        int day=0;LL cost=0,mov=0,left=0,ans;
        for(int i=1;i<=n;++i) ++student[t=read()],day=max(day,t);
        for(int i=1;i<=m;++i) ++course[t=read()],day=max(day,t);
        for(int i=1;i<=day;++i) cost+=student[i]*(day-i),left+=course[i]*(day-i),student[i]+=student[i-1],course[i]+=course[i-1];
       ans=cost*c;
        for(int i=day-1;i>0;i--)
        {
            mov+=(m-course[i]);
            left-=course[i];
            cost-=student[i];
            if(c>=INF&&cost)continue;
            LL p=left>0?left:0;
            if(mov<p)p=mov;
            if(a<b)ans=min(ans,p*a+(mov-p)*b+cost*c);
            else ans=min(ans,mov*b+cost*c);
        }
        printf("%lld\n",ans);
        return 0;
    } 
    

Task 2 Verbinden 相逢是问候

题面

问题描述

Informatik verbindet dich und mich.

信息将你我连结。

B君希望以维护一个长度为 nn 的数组,这个数组的下标为从 11nn 的正整数。

一共有 mm 个操作,可以分为两种:

0 l r0\ l\ r 表示将第 ll 个到第 rr 个数( al,al+1,,ara_l, a_{l+1}, \ldots, a_r )中的每一个数 aia_i 替换为 caic^{a_i} ,即 ccaia_i 次方,其中 cc 是输入的一个常数,也就是执行赋值

ai=caia_i = c^{a_i}

1 l r1\ l\ r 求第 ll 个到第 rr 个数的和,也就是输出:

i=lrai\sum_{i=l}^r a_i

因为这个结果可能会很大,所以你只需要输出结果 $ mod\ p$ 的值即可。

输入格式

第一行有三个整数 n,m,p,cn, m, p, c ,所有整数含义见问题描述。

接下来一行 nn 个整数,表示 aa 数组的初始值。

接下来 mm 行,每行三个整数,其中第一个整数表示了操作的类型。

如果是 0 的话,表示这是一个修改操作,操作的参数为 l,rl,r

如果是 1 的话,表示这是一个询问操作,操作的参数为 l,rl,r

输出格式

对于每个询问操作,输出一行,包括一个整数表示答案 mod pmod\ p 的值。

子任务

  • 对于 0%0\% 的测试点,和样例一模一样;
  • 对于另外 10%10\% 的测试点,没有修改;
  • 对于另外 20%20\% 的测试点,每次修改操作只会修改一个位置(也就是 l=rl=r ),并且每个位置至多被修改一次;
  • 对于另外 10%10\% 的测试点,p=2p=2
  • 对于另外 10%10\% 的测试点,p=3p=3
  • 对于另外 10%10\% 的测试点,p=4p=4
  • 对于另外 20%20\% 的测试点,n100,m100n \leq 100, m \leq 100
  • 对于 100%100\% 的测试点, 1n50000,1m50000,1p100000000,0<c<p,0ai<p1 \leq n \leq 50000, 1 \leq m \leq 50000, 1 \leq p \leq 100000000, 0 < c < p, 0 \leq a_i < p

解法

毕克的锅:数据错,数据错,数据错完题解错。

部分分

  1. 对于 10%10\% 的测试点,可以直接使用前缀和。

  2. 对于 30%30\% 的测试点,可以用线段树。

  3. 考虑 p=2p=2 , $ p=3 $ , $ p=4 $ 。

    $ p=2 $ 时,对于 $ a_i = 5 $ ,令 $ c=2 $ 一定有 $ 4^{a_i} \equiv 0 (mod\ 2)$ ,以后 $ 4^{a_i} $ 即一直等于0。事实上,通过观察可以发现,这种情况对于任何的 $ c $ 和 $ p $ 都是必然发生的。其宽松上界是 $ 2\ log\ p $ 。那么按版本建线段树,(虽然听上去像主席树,但并不需要如此复杂。),即可通过 60%60\% 的测试点。

一个较难的部分分和正解

之所以放在一起讲,是因为这两者是相关的。

Theorem I 欧拉定理

对于满足 $ gcd(p,m) = 1 , p,m\in Z^+ $,有 $ a^{\phi(m)} \equiv 1 (mod\ m)$

Theorem II 推广版本的欧拉定理

对于任意 $ p,m,x \in Z^+ 且保证x>\phi(p)$时,有 $ a^x \equiv a^{\phi(p)+x\ mod \phi(p)}(mod\ p) $

证明:参见张晴川的知乎https://zhuanlan.zhihu.com/p/24902174

题外话:费马小定理:对于素数 $ p $ ,有 $ a^p \equiv a (mod\ p) $。用这个定理可以计算逆元,也是Miller- Rabin算法的基础。

迭代 Theorem II 即可。

考虑欧拉函数,对于$ \phi(\phi(x)) $ ,明显以比 $ log $阶更快的速度迭代到足够小。那么的话,我们可以考虑暴力修改。这样可以获得这 $ 20% $的分数。

那么随后考虑如何维护。区间修改的线段树有一个常用技巧,即惰性标记。但此题中无从标记,但考虑到每次最多修改 $ 2\ log\ p $ 次,那么在线段树上强行暴力修改即可。考虑快速幂,发现可能会被快速幂强行卡常,期望复杂度 $ O( n\ log\ n\ log\ p) $由于数据范围较小,也可分块处理。

这里对于毕克的锅做一个总结,在 std 中和题解中,毕克在处理最后的展开的时候,忘记多展开一层,即 $ \phi (1) = 1 $ 。导致大样例 II & III 以及大量数据出错。立此存照。

TODO:是否使用分块维护会更快?

我想是可能的,分块理论上可以O(1)修改,O(sqrt(N))查询,在修改多而查询少的时候也许可以起到加速的作用。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?a:b)
#define MAXN 100020
int a[MAXN],*w[30],N=5000000,b[MAXN],s[MAXN<<2],c[MAXN<<2],f[32][65537],g[32][65537],n,m,p[100],q,r;
void build(int x,int l,int r){
	if(l+1==r) {
		s[x]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid),build(x<<1|1,mid,r);
	s[x]=(s[x<<1]+s[x<<1|1])%p[0];
}
int query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return s[x];
	if(r<=L||R<=l) return 0;
	int mid=(l+r)>>1;
	return (query(x<<1,l,mid,L,R)+query(x<<1|1,mid,r,L,R));
}
int mul(int x, int y, int p){
	if(1LL*x*y<p) return x*y;
	else return 1LL*x*y%p+p;
}
int pw(int x,int y,int z){
	return mul(f[z][y&((1<<16)-1)],g[z][y>>16],p[z]);
}
int A(int x,int y){
	int *s[64]={},ss=0;
	for(int i=y-1;i>=0;--i){
		if(0<=x&&x<N&&x<2*p[i]){
			if(w[i][x]!=-1) {
				x=w[i][x];
				break;
			}
			s[ss++]=&w[i][x];
		}
		x=pw(r,x,i);
	}
	for(int i=0;i<ss;++i) *s[i]=x;
	return x;
}
void change(int x, int l, int r, int L, int R) {
	if(c[x]==r-l) return;
	if(r<=L||R<=l) return;
	if (l+1==r) {
		s[x]=A(a[l],++b[l]);
		if (b[l] == q) c[x] = 1;
		return;
	}
	int m=(l+r)/2;
	change(2*x,l,m,L,R);
	change(2*x+1,m,r,L,R);
	s[x]=(s[2*x]+s[2*x+1])%p[0];
	c[x]=(c[2*x]+c[2*x+1]);
}
int phi(int x){
	int ret=x;
	for(int i=2;i*i<=x;++i)
		if(!(x%i)){
			ret=ret/i*(i-1);
			while(!(x%i)) x/=i;
		}
	if(x>1) ret=ret/x*(x-1);
	return ret;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&p[0],&r);
	q=0;
	while(p[q]>1) p[++q]=phi(p[q-1]);
	p[++q]=1;
	for(int i=0;i<=q;++i){
		int length=min(N,p[i]*2);
		w[i]=new int[length];
		memset(w[i],-1,sizeof(int)*length);
	}
	for(int j=0;j<=q;++j){
		f[j][0]=1;
		for(int i=1;i<=1<<16;++i) f[j][i]=mul(f[j][i-1],r,p[j]);
		g[j][0]=1;
		for(int i=1;i<=1<<16;++i) g[j][i]=mul(g[j][i-1],f[j][1<<16],p[j]);
	}
	for(int i=0;i<n;++i) scanf("%d",a+i);
	build(1,0,n);
	for(int i=0,o,x,y;i<m;++i){
		scanf("%d%d%d",&o,&x,&y);
		--x;
		if(!o) change(1,0,n,x,y);
		else if(o==1) printf("%d\n",query(1,0,n,x,y)%p[0]);
	}
	return 0;
}

Task 3 problem 组合数问题

题面

问题描述

组合数 CnmC_n^m 表示的是从 nn 个互不相同的物品中选出 mm 个物品的方案数。举个例子,从 (1,2,3)(1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 CnmC_n^m 的一般公式:

Cnm=n!m!(nm)!C_n^m=\frac{n!}{m!(n-m)!}

其中 n!=1×2××nn!=1\times2\times\cdots\times n。(特别的,当 n=0n=0 时, n!=1n!=1 ,当 m>nm>n 时,Cnm=0C_n^m=0

小葱在NOIP的时候学习了 CijC_i^jkk 的倍数关系,现在他想更进一步,研究更多关于组合数的性质。小葱发现,CijC_i^j 是否是 kk 的倍数,取决于 CijmodkC_i^j \bmod k 是否等于 00,这个神奇的性质引发了小葱对 mod\bmod 运算(取余数)的兴趣。现在小葱选择了是四个整数 n,p,k,rn,p,k,r,小葱现在希望知道

(i=0Cnkik+r)modp\left(\sum_{i=0}^{\infty}C_{nk}^{ik+r}\right)\bmod p

(Cnkr+Cnkk+r+Cnk2k+r++Cnk(n1)k+r+Cnknk+r+)modp\left(C_{nk}^r+C_{nk}^{k+r}+C_{nk}^{2k+r}+\cdots+C_{nk}^{(n-1)k+r}+C_{nk}^{nk+r}+\cdots\right)\bmod p

的值。

输入格式

第一行有四个整数 n,p,k,rn,p,k,r,所有整数含义见问题描述。

输出格式

一行一个整数代表答案。

任务

  • 对于 30%30\% 的测试点,1n,k301\leq n,k\leq 30pp 是质数;
  • 对于另外 5%5\% 的测试点,p=2p=2
  • 对于另外 5%5\% 的测试点,k=1k=1
  • 对于另外 10%10\% 的测试点,k=2k=2
  • 对于另外 15%15\% 的测试点,1n103,1k501\leq n\leq 10^3,1\leq k\leq 50pp 是质数;
  • 对于另外 15%15\% 的测试点,1n×k1061\leq n\times k\leq 10^6pp 是质数;
  • 对于另外 10%10\% 的测试点,1n109,1k501\leq n\leq 10^9,1\leq k\leq 50pp 是质数;
  • 对于 100%100\% 的测试点, 1n109,0r<k50,2p23011\leq n\leq 10^9,0\leq r<k\leq 50,2\leq p\leq 2^{30}-1

解法

部分分

  1. 对前 30%30\% 的点,强行用定义暴力即可。

  2. 对于前 30%30\% 的点和 $1 \leq n \leq 10^3 , 1 \leq k \leq 50 $ 的 15%15\% 点,可以参考NOIP2016 Day2T1的 95%95\% 解法,即模意义下的杨辉三角形,然后在杨辉三角形上强行求和。

    #include <stdio.h>
    #include <string.h>
    int C[1010][1010],n,p,k,r,Ans=0;
    int main(){
    	scanf("%d%d%d%d",&n,&p,&k,&r);
    	memset(C,0,sizeof(C));
    	C[0][0]=1;
    	for(int i=1;i<=n*k;++i){
    		C[i][0]=1;
    		for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    	}
    	for(int i=r;i<=n*k;i+=k) Ans=(Ans+C[n*k][i])%p;
    	printf("%d\n",Ans);
    	return 0;
    }
    

  3. 对于一些零散的点,考虑组合数的构造,我们可以发现,对组合数取倒数,分母归一,解决分子,将分母取逆元后乘回去,再将全体取逆元即可。实践证明可以获得 60%60\% 的分数。

正解

定义函数 f(n,r)f(n,r) 为从 nknk 个元素中取出模 kkrr 个元素的方案数。那么对其展开,化简。

f(n,r)=iCnkik+r=it=0kC(n1)kik+rt×Ckt=t=0kCktiC(n1)kik+rt=t=0kCktf(n1,rt)f(n,r) = \sum_i C^{ik+r}_{nk} = \sum_i \sum_{t=0}^k C^{ik+r-t}_{(n-1)k} \times C^t_k = \sum_{t=0}^{k} C^t_k \sum_i C^{ik+r-t}_{(n-1)k} = \sum_{t=0}^{k} C_k^t f(n-1,r-t)

然而这样是不够的,化简成这个形式以后,注意到可以构造出两个矩阵 AABB ,分别表示组合数系数和 n1n-1 情况下的 f(n1,rt)f(n-1,r-t) 。那么每一次转移都可以表示为 A 的幂。考虑矩阵快速幂,由于 k 50k\leq\ 50 ,即可在 O(k3logn)O(k^3logn) 的复杂度解决此题。如果把矩阵快速幂转换为线性形式,那么可以更优。

#include <stdio.h>
#include <string.h>
#define MAXK 50+5

int n,p,k,r;
int A[MAXK][MAXK],temp[MAXK][MAXK],Ans[MAXK][MAXK];
int C[MAXK][MAXK];
void calc_c(int n){
	memset(C,0,sizeof(C));
	C[0][0]=1;
	for(int i=1;i<=n;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
}

int main(){
	scanf("%d%d%d%d",&n,&p,&k,&r);
	calc_c(k);
	for(int i=0;i<k;++i)
		for(int j=0;j<=k;++j)
			(A[(i+j)%k][i]+=C[k][j])%=p;
	memset(Ans,0,sizeof(Ans));
	for(int i=0;i<k;++i)
		Ans[i][i]=1;
	while(n){
		if(n&1){
			//Ans*=T
			for(int i=0;i<k;++i)
				for(int j=0;j<k;++j){
				temp[i][j]=0;
					for(int l=0;l<k;++l)
						temp[i][j]=(1LL*Ans[i][l]*A[l][j]+temp[i][j])%p;
				}
			for(int i=0;i<k;++i)
				for(int j=0;j<k;++j)
					Ans[i][j]=temp[i][j];
		}
		//T*=T
		for(int i=0;i<k;++i)
			for(int j=0;j<k;++j){
				temp[i][j]=0;
				for(int l=0;l<k;++l)
					temp[i][j]=(1LL*A[i][l]*A[l][j]+temp[i][j])%p;
			}
		for(int i=0;i<k;++i)
			for(int j=0;j<=k;++j)
				A[i][j]=temp[i][j];
		n>>=1;
	}
	printf("%d\n",Ans[r][0]);
	return 0;
}