C

可以把图形画成一个大等边三角形,如图
cf313
一个边长为n的大三角形含有$n^2$个小三角形,我们很容易可以计算出
ans = (a[0]+a[1]+a[2])^2- (a[0])^2- (a[2])^2 - (a[4])^2
当然,想不到的话可以算面积呀。,。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int a[6];
inline int P(int a)
{
return a*a;
}

int main()
{
//freopen("test.txt","r",stdin);
for(int i=0;i<6;++i) scanf("%d",a+i);
printf("%d\n",P(a[0]+a[1]+a[2])-P(a[0])-P(a[2])-P(a[4]));
return 0;
}

D

直接暴力比较都能过…
不过我加了一个字符串和的hash优化跑的非常快…
题解方法是将字符串排列成等价的最小字典序

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 2e5 + 10;
char s1[maxn],s2[maxn];
int sum1[maxn],sum2[maxn];
int n;

bool check(int l1,int r1,int l2,int r2)
{
if((r1 - l1)&1)
{
if(sum1[r1+1] - sum1[l1] != sum2[r2+1] - sum2[l2]) return false;
int m1 = (l1+r1)>>1,m2 =(l2+r2)>>1;
return (check(l1,m1,l2,m2) && check(m1+1,r1,m2+1,r2)) || (check(l1,m1,m2+1,r2) && check(m1+1,r1,l2,m2));
}
else
{
int p1 = l1,p2 = l2;
while(p1 <= r1)
{
if(s1[p1] != s2[p2]) return false;
++p1;
++p2;
}
return true;
}
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%s %s",s1,s2);
n = strlen(s1);
sum1[0] = sum2[0] = 0;
for(int i=0;i<n;++i)
{
sum1[i+1] = sum1[i] + s1[i] - 'a';
sum2[i+1] = sum2[i] + s2[i] - 'a';
}
puts(check(0,n-1,0,n-1)?"YES":"NO");
return 0;
}

  • 题解方法
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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

string smallest(string s)
{
if (s.length()&1) return s;
string s1 = smallest(s.substr(0,s.length()/2));
string s2 = smallest(s.substr(s.length()/2,s.length()));
if (s1 < s2) return s1 + s2;
else return s2 + s1;
}

int main()
{
//freopen("test.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
string s1,s2;
cin>>s1>>s2;
s1 = smallest(s1);
s2 = smallest(s2);
puts(s1 == s2?"YES":"NO");
return 0;
}

E

我们将黑色格子 先x后y 排序
最后一个格子设为终点
我们考虑$d_i$ 为到达第i个格子,且之前不经过任何黑色格子的点的方案数
$$d_i = C_{x_i + y_i - 2}^{x_i - 1} - \sum_{j<i , x_j \le x_i, y_j \le y_i} C_{x_i +- x_j + y_i - y_j}^{x_i - x_j}d_j$$

可以理解为第一个经过的黑格子为i的方案
我们需要提前处理出阶乘来加速组合数的运算,注意h,w较大时要用lucas定理计算组合数

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
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
int h,w,n;

const int maxn = 2010;
const int mod = int(1e9) + 7;

struct P
{
int x,y;
P() {}
P(int x,int y):x(x),y(y) {}
bool operator<(const P& rhs) const
{
return x<rhs.x || (x == rhs.x && y<rhs.y);
}
} p[maxn];
LL fac[200010];

LL qpow(LL a,int n)
{
LL res = 1;
while(n)
{
if(n&1) res = res*a % mod;
a = a*a % mod;
n >>= 1;
}
return res;
}

LL C(LL n,LL m)
{
if(m == 0) return 1;
return fac[n]*qpow(fac[n-m]*fac[m]%mod,mod - 2)%mod;
}

LL d[maxn];


int main()
{
//freopen("test.txt","r",stdin);
fac[0] = 1;
for(int i=1;i<200010;++i) fac[i] = fac[i-1] * i % mod;
scanf("%d %d %d",&h,&w,&n);
for(int i=0;i<n;++i)
{
int x,y;
scanf("%d %d",&x,&y);
p[i] = P(x,y);
}
sort(p,p+n);
if(p[n-1].x == h && p[n-1].y == w || p[0].x == 1 && p[0].y == 1) puts("0");
else
{
p[n].x = h ;
p[n].y = w ;
memset(d,0,sizeof d);
for(int i=0;i<=n;++i)
{
d[i] = C(p[i].x+p[i].y-2,p[i].x-1);
for(int j=0;j<i;++j)
{
if(p[j].y <= p[i].y)
{
d[i] = (d[i] - C(p[i].x - p[j].x + p[i].y - p[j].y,p[i].x - p[j].x)*d[j])%mod;
}
}
}
d[n] = (d[n]%mod + mod) % mod;
printf("%lld\n",d[n]);
}
return 0;
}