A - 求递推序列的第N项

矩阵快速幂,帮助大家搭建/测试自己的模板。
简单地讲一下原理,可以看到每一项用到了前两项的值,首先构造一个二维的向量$\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)$,如果有常数就再加一维。那么将这个向量作为自变量,下一项就是$\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$。最后稍微动一下脑子配一个$2\times2$的系数矩阵使得$Cx_{i-1}=x_{i}$:
$$\left(\begin{matrix}
A & B \\
1 & 0 \\
\end{matrix}\right)
\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)
=\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$$
复杂度$O(M^3logN)$,其中$M$为矩阵的大小,等于$2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MO=7;
struct Matrix {
int r,c;
ll e[2][2];
Matrix() {}
Matrix(int _r,int _c) {
r=_r;c=_c;
memset(e,0,sizeof(e));
}
Matrix(ll x) {
r=c=2;
memset(e,0,sizeof(e));
for (int i=0;i<r;i++) {
e[i][i]=x;
}
}
Matrix operator *(const Matrix &b) {
Matrix C(r,b.c);
for (int i=0;i<r;i++) {
for (int j=0;j<b.c;j++) {
for (int k=0;k<c;k++) {
C.e[i][j]+=e[i][k]*b.e[k][j]%MO;
if (C.e[i][j]>=MO) C.e[i][j]%=MO;
}
}
}
return C;
}
};
Matrix fpow(Matrix x,ll n)
{
Matrix res(1);
while (n) {
if (n&1) {
res=res*x;
}
x=x*x;
n>>=1;
}
return res;
}
int main()
{
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
if (n<=2) {
puts("1");
} else {
Matrix A(2,2);
A.e[0][0]=a;
A.e[0][1]=b;
A.e[1][0]=1;
A.e[1][1]=0;
Matrix X(2,1);
X.e[0][0]=1;
X.e[1][0]=1;
A=fpow(A,n-2);
X=A*X;
int ans=(X.e[0][0]%MO+MO)%MO;
printf("%d\n",ans);
}
return 0;
}

B - Kinds of Fuwas

题意:四个角为同一种福娃的子矩形有多少个?
题解:从样例可以看出,一行或一列的矩形都不算。从数据范围来看,直接四个循环复杂度太高了,但是每个元素的值域很小,只有五个种类,所以可以考虑枚举每个种类来做。对于每个种类,比如H,我们可以利用类似最大子矩阵的套路,枚举两行作为上下界,然后再枚举每一列,对上下都是H的列进行计数,在这之中任取两列就是符合要求的矩形,所以把答案加上$C^{2}_{m}$即可,这个组合数可以$O(1)$求得。
复杂度$(KM^2N)$,其中$K$等于$5$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const char PP[9]="BJHYN";
const int N=256;
char mp[N][N];
int main()
{
int T;
scanf("%d",&T);
while (T--) {
int n,m;
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) {
scanf("%s",mp[i]);
}
long long ans=0;
for (int p=0;p<5;p++) {
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
int t=0;
for (int k=0;k<m;k++) {
if (mp[i][k]==PP[p]&&mp[j][k]==PP[p]) ++t;
}
ans+=t*(t-1)/2;
}
}
}
printf("%lld\n",ans);
}
return 0;
}

C - GCD is Funny

题意:
在黑板上写有$n$个数,每次删掉$a,b,c$三个数并把$d$写两遍,$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数,输出这个数的所有可能情况。

题解:
这个题很难虽然出在某一场BC的A题
首先要思考一下脱离具体过程,这个数到底是什么。题中的过程以下简称为“擦黑板”。

  1. 如果已经存在两个相同的数$x$,再取一个数$y$进行一次擦黑板,那么可以令$d=(x,x)=x$,剩下的数为$x,x$。可以发现$y$没有产生影响,两个$x$直接“吃掉”了$y$;
  2. 由1,我们可以单独考虑每一个$size\ge 3$的子集,它的结果一定是两个相同的数,其他的数直接吃掉就好。为了保证枚举的不重不漏,该子集内应该有尽量多的数参与$gcd$运算(注意,参与擦黑板$\neq$参与$gcd$运算),也就是$size-1$个数。因为第一次擦黑板一定有一个数无法参与$gcd$运算,而从第二次开始,有前一次得到的两个数$x$,再取一个数$y$进行一次擦黑板,那么可以令$d=(x,y)$,$y$一定能参与$gcd$运算。

综上,最后留在黑板上的数其实是任意一个$2\le size \le n-1$的子集的所有数的$gcd$。

接着再思考一下怎么巧妙地求出这些数,因为暴力枚举子集肯定是不行的。
首先注意到$a_i$的值域只有$1000$,而且$gcd$运算只会变小,所以这实际上也是答案的值域。
其次$gcd$有一个更强的性质,两个不一样的数取$gcd$,最大也只能是大数的一半。(为什么?)
所以我们写一个比较暴力的方法也能保证复杂度,最后要注意的一点就是不要取到全集,具体可以看代码。
复杂度$O(n^2+nV\cdot min(log(V),n-3))$,$V$为$a_i$的值域。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int MAX=1000;
int a[510];
bool b[MAX+5];
int main()
{
int T;
scanf("%d",&T);
while (T--) {
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
memset(b,0,sizeof(b));
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
b[__gcd(a[i],a[j])]=true;
}
}
int num=2;
bool flag=true;
while (++num<n && flag) {
flag=false;
for (int i=1;i<=MAX;i++) {
if (b[i]) {
for (int j=1;j<=n;j++) {
int y=__gcd(i,a[j]);
if (!b[y]) {
b[y]=true;
flag=true;
}
}
}
}
}
bool fi=true;
for (int i=1;i<=1000;i++) {
if (b[i]) {
if (fi) {
printf("%d",i);
fi=false;
} else {
printf(" %d",i);
}
}
}
puts("");
}
return 0;
}

D - Ant

题意:蚂蚁在一个长方体表面从起点爬到对角点的最短长度设为$L$,问所有最长边是$n$的长方体的$L^2$之和。
题解:出这题主要是想让大家牢记三个求和公式。
$$ \sum_{i=1}^{n}{i} = \frac{n(n+1)}{2} \\
\sum_{i=1}^{n}{i^2} = \frac{n(n+1)(2n+1)}{6} \\
\sum_{i=1}^{n}{i^3} = (\sum_{i=1}^{n}{i})^2 = \frac{n^2(n+1)^2}{4} $$
在表面上的路径实际上就是三种展开,所以$L^2=\min\{(x+y)^2+n^2,(n+x)^2+y^2,(n+y)^2+x^2\}$,因为在这个式子中$x+y+n$为定值,那么自然是两个数越接近越小,又有$x,y\le n$,所以$L^2=(x+y)^2+n^2$。
$$\begin{equation}\begin{split}
Ans &= \sum_{x=1}^{n}{\sum_{y=1}^{x}{(x+y)^2+n^2}} \\
&= \sum_{x=1}^{n}{x^3+n^2x+x^2(x+1)+\frac{x(x+1)(2x+1)}{6}} \\
&= \sum_{x=1}^{n}{\frac{7}{3}x^3+\frac{3}{2}x^2+(\frac{1}{6}+n^2)x} \\
&= \frac{7}{3}\frac{n^2(n+1)^2}{4}+\frac{3}{2}\frac{n(n+1)(2n+1)}{6}+(\frac{1}{6}+n^2)\frac{n(n+1)}{2} \\
&= \frac{1}{12}(13n^4+26n^3+17n^2+4n)
\end{split}\end{equation}$$
然后就是求个逆元乘一乘模一模就行了。
复杂度$O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MO=1000000007;
ll fpow(ll x,ll n)
{
ll res=1;
for (;n;n>>=1,x=x*x%MO) {
if (n&1) res=res*x%MO;
}
return res;
}
int main()
{
ll INV12=fpow(12,MO-2);
int T;
scanf("%d",&T);
while (T--) {
ll n;
scanf("%lld",&n);
n%=MO;
printf("%lld\n",n*(4+n*(17+n*(26+n*13%MO)%MO)%MO)%MO*INV12%MO);
}
return 0;
}

E - RPG的错排

首先预处理错排数和组合数,然后枚举一下猜错了多少人。
单组复杂度$O(n)$。
错排数的通项和递推式请参阅其他资料。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=26;
ll cp[N],C[N][N];
int main()
{
cp[0]=1;
for (int i=2;i<N/2;i++) {
cp[i]=(cp[i-2]+cp[i-1])*(i-1);
}
for (int i=0;i<N;i++) {
C[i][0]=1;
for (int j=1;j<=i;j++) {
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
int n;
while (scanf("%d",&n)!=EOF&&n) {
ll ans=0;
for (int i=0;i<=n/2;i++) {
ans+=C[n][i]*cp[i];
}
printf("%lld\n",ans);
}
return 0;
}

F - Dertouzos

题意:$n$的真因子是不为$n$的因子。给出$n$和$d$,问有多少小于$n$的数的最大真因子是$d$。
题解:即$pd=m\lt n$,显然有

  1. $p \le \frac{n-1}{d}$;
  2. $p$必须为质数;(如若不然,则$p$有真因子$q$,$qd$是比$d$更大的$m$的真因子。)
  3. $p \le c$,其中$c$为$d$的最小质因子。(如若不然,则$\frac{d}{c}\times p$是比$d$更大的$m$的真因子。)

由2,我们先做一遍筛法以及前缀和。再算出1的界,最后用筛出来的质数去算3的界。

注意点:用筛出来的质数去算3的界会有$O(\sqrt{d})$的复杂度,当$d$一直很大($\approx 10^{9}$)时会超时,而此时1的界必然比较小,应该在超过已有的界时及时退出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int MAX=100010;
int tot=0,prime[100000];
bool isprime[MAX];
int sum[MAX];
void init()
{
memset(isprime,1,sizeof(isprime));
isprime[1]=false;
for(int i=2; i<MAX; i++) {
if(isprime[i])prime[++tot]=i;
for(int j=1; j<=tot&&i*prime[j]<MAX; j++) {
isprime[i*prime[j]]=false;
if(i%prime[j]==0)break;
}
}
for (int i=2;i<MAX;i++) {
sum[i]=sum[i-1]+isprime[i];
}
}
int T,n,d;
int getmaxp()
{
for (int i=1;i<=tot;i++) {
if (prime[i]>(n-1)/d) return prime[i-1];
if (d%prime[i]==0) return prime[i];
if (prime[i]*prime[i]>d) return min(d,(n-1)/d);
}
return -1;
}
int main()
{
init();
scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&d);
printf("%d\n",sum[getmaxp()]);
}
return 0;
}

ps. 其实有一个更显然的做法,直接依次枚举质数即可。

G - One Person Game

抽象一下,有方程$ax+by+cz=B-A$成立,其中$c=a+b$,求$|x|+|y|+|z|$的最小值。
有个结论不太会证,简单来说,$x,y,z$均不为$0$时不会比有一个为$0$时更好。(把$a+b$变成$c$或者把$c$拆掉)
那么其实就是求满足$ax+by=C$的$|x|+|y|$的最小值,然后修改系数求三遍比较一下。
当$x,y$异号时,显然是让$x,y$都尽量接近0;当$x,y$同号时,因为系数都是正的,其实也是在$x$最接近$0$或者$y$最接近$0$的时候取到极值。
综上,我们只要分别考虑$x$最接近$0$和$y$最接近$0$的情况,各有两个。又因为C/C++的整除符号在被除数是负数时不是向下取整,我们可以更暴力地每次考虑三种情况。
复杂度$O(logV)$,$V$为$a,b$的值域大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF=1LL<<60;
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
if(a==0&&b==0) return -1;//无最大公约数
if(b==0) {
x=1;
y=0;
return a;
}
long long d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll calc(ll x,ll y)
{
return abs(x)+abs(y);
}
ll solve(ll a,ll b,ll c)
{
ll x,y,t;
ll g=extend_gcd(a,b,x,y);
if (c%g) return INF;
a/=g;b/=g;c/=g;
x*=c;y*=c;
t=x/b;x-=b*t;y+=a*t;
ll res=calc(x,y);
res=min(res,calc(x-b,y+a));
res=min(res,calc(x+b,y-a));
t=y/a;x+=b*t;y-=a*t;
res=min(res,calc(x,y));
res=min(res,calc(x+b,y-a));
res=min(res,calc(x-b,y+a));
return res;
}
int main()
{
int T;
scanf("%d",&T);
while (T--) {
ll A,B,a,b;
scanf("%lld%lld%lld%lld",&A,&B,&a,&b);
ll ans=solve(a,b,B-A);
ans=min(ans,solve(a,a+b,B-A));
ans=min(ans,solve(b,a+b,B-A));
if (ans==INF) puts("-1");
else printf("%lld\n",ans);
}
return 0;
}