17.10.25

上午

模拟考试
Prob.1（AC）用用<cmath>里的sin和cos就好

注意一个细节：因为double的精度问题，输出0是可能会输出-0。

要特判一下。

Prob.2（WA）矩阵幂优化线性递推，但我制杖地把递推写错了一个地方。

考试时有多余时间一定要写暴力对拍啊，（可恶的万能样例竟然还过了）

Prob.3（70）正解是线段树优化dp，（用线段树维护一个区间的最大值，log₂n级别转移）

我写了一个差分约束（用的裸的spfa），过了70分。但之后把spfa用双端队列deque或者优先队列优化以后，就快得飞起来，比正解（线段树+dp，这个差分约束也算正解了吧）还快。

下午

改了改题，学了学上午考试第三题正解
BOZJ 1072 半天没搞出来，效率太低了。
、、、

晚上

BOZJ 1072 [SCOI2007]排列perm

dp[s][j]:表示s这个集合中的数构成的对d取模后等于j的数有多少个。
然后有一个小结论：
若 j=A%d，令 x=(A*10+B)%d,则 (j*10+B)%d==x
这个也很显然：
令 A=k*d+j,
则 x=((k*d+j)*10+B)%d
=(k*d*10+j*10+B)%d
=(j*10+B)%d
所以转移如下：
dp[s|(1<<k)][(j*10+s[k]-'0')%d]+=dp[s][j];
最后处理一下出现多次的数字。因为不考虑相同数字的顺序，所以除以其出现次数的阶乘。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s[15];
int dp[1<<10][1005],c[15],fac[15];
int T,d,n;
int idx(char ch){
	return ch-'0';
}
int main(){
	scanf("%d",&T); fac[0]=1;
	for(int i=1;i<=10;i++) fac[i]=fac[i-1]*i;
	while(T--){
		scanf("%s",s);
		scanf("%d",&d);
		memset(dp,0,sizeof(dp));
		dp[0][0]=1; n=strlen(s);
		for(int i=0;i<(1<<n);i++)
			for(int j=0;j<d;j++){
				if(!dp[i][j]) continue;
				for(int k=0;k<n;k++){
					if(i&(1<<k)) continue;
					dp[i|(1<<k)][(j*10+idx(s[k]))%d]+=dp[i][j];
				}
			}
		memset(c,0,sizeof(c));
		for(int i=0;i<n;i++) c[idx(s[i])]++;
		for(int i=0;i<10;i++) dp[(1<<n)-1][0]/=fac[c[i]];
		printf("%d
",dp[(1<<n)-1][0]);
	}
	return 0;
}

BZOJ 1073 还没打完……

今天效率是真的低啊！再这样下次考试就要爆零了。