比赛链接
1001 Road To The 3rd Building
显然，
其中分子的化简如下：
枚举 $l$，预处理之后分段计算 $k$ 即可。
时间复杂度：$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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
const LL MOD = 1e9+7;
int n;
LL a[N], sum[N], kak[N], inv[N];
int main(){
inv[1] = 1; for(int i = 2; i <= 200001; i++){
inv[i] = -(MOD / i) * inv[MOD % i];
((inv[i] %= MOD) += MOD) %= MOD;
}
int T; for(read(T); T; T--){
read(n);
for(int i = 1; i <= n; i++){
read(a[i]);
sum[i] = (sum[i-1] + a[i]) % MOD;
kak[i] = (kak[i-1] + i * a[i]) % MOD;
}
LL ans = 0;
for(int l = 1; l <= n; l++){
LL res = 0;
int k1 = min(l, n - l + 1), k2 = max(l, n - l + 1);
(res += kak[k1]) %= MOD;
if(l > n - l + 1) (res += (n - l + 1ll) * (sum[k2] - sum[k1]) % MOD) %= MOD;
else if(l < n - l + 1) (res += l * (sum[k2] - sum[k1]) % MOD) %= MOD;
(res += (n + 1ll) * (sum[n] - sum[k2]) % MOD - (kak[n] - kak[k2]) % MOD) %= MOD;
((res %= MOD) += MOD) %= MOD;
(res *= inv[l]) %= MOD;
(ans += res) %= MOD;
}
ans = ans * inv[n] % MOD * inv[n+1] % MOD * 2ll % MOD;
printf("%lld\n", ans);
}
return 0;
}
|
1002 Little Rabbit’s Equation
模拟。
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int n, f[1005];
char s[105];
inline bool check(LL bs){
for(int i = 1; i <= n; i++){
if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '=') continue;
if(f[s[i]] >= bs) return false;
}
LL a = 0, b = 0, c = 0;
LL *t = &a;
int kind = 0;
for(int i = 1; i <= n; i++){
if(s[i] == '+'){ kind = 1; t = &b; continue; }
else if(s[i] == '-'){ kind = 2; t = &b; continue; }
else if(s[i] == '*'){ kind = 3; t = &b; continue; }
else if(s[i] == '/'){ kind = 4; t = &b; continue; }
else if(s[i] == '='){ t = &c; continue; }
(*t) = (*t) * bs + f[s[i]];
}
if(kind == 1) return a + b == c;
else if(kind == 2) return a - b == c;
else if(kind == 3) return a * b == c;
else if(kind == 4) return a == b * c;
return false;
}
int main(){
for(int i = 0; i <= 9; i++) f[i+'0'] = i;
for(int i = 'A'; i <= 'F'; i++) f[i] = i - 'A' + 10;
while(scanf("%s", s+1) != EOF){
n = strlen(s+1);
bool ok = false;
for(int b = 2; b <= 16; b++){
if(check(b)){
ok = true;
printf("%d\n", b);
break;
}
}
if(!ok) puts("-1");
}
return 0;
}
|
1005 Fragrant numbers
明天再写
1006 A Very Easy Graph Problem
由于边权都是 $2^i$ 且互不相同，依据题目输入顺序，两个点之间的最短路就是它们一旦连通的时候的路径。也就是说，根据加的边做生成树即可。
接下来就是一个 $\text{dp}$ 了，计算以 $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
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
const LL MOD = 1e9+7;
LL power[N<<1] = {1};
int n, m, a[N], sum[2];
vector<pii> edge[N];
int fa[N];
int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
void unionn(int x, int y){ fa[findfa(y)] = findfa(x); }
int dp[N][2];
LL ans;
void dfs(int x, int f){
dp[x][a[x]] = 1;
for(auto &to : edge[x]){
if(to.first == f) continue;
dfs(to.first, x);
dp[x][0] += dp[to.first][0];
dp[x][1] += dp[to.first][1];
(ans += dp[to.first][0] * (sum[1] - dp[to.first][1]) % MOD * power[to.second] % MOD) %= MOD;
(ans += dp[to.first][1] * (sum[0] - dp[to.first][0]) % MOD * power[to.second] % MOD) %= MOD;
}
}
inline void initCASES(){
sum[0] = sum[1] = ans = 0;
for(int i = 1; i <= n; i++){
fa[i] = i;
edge[i].clear();
dp[i][0] = dp[i][1] = 0;
}
}
int main(){
for(int i = 1; i <= 200000; i++) power[i] = power[i-1] * 2 % MOD;
int T; for(read(T); T; T--){
read(n, m);
initCASES();
for(int i = 1; i <= n; i++) read(a[i]), sum[a[i]]++;
for(int i = 1; i <= m; i++){
int u, v; read(u, v);
if(findfa(u) == findfa(v)) continue;
unionn(u, v);
edge[u].pb(mp(v, i)), edge[v].pb(mp(u, i));
}
dfs(1, 0);
printf("%lld\n", ans);
}
return 0;
}
|
1007 A Very Easy Math Problem
推不动了，于是把 $\sum\limits_{d\mid T}d\mu^2(d)\mu\left(\frac{T}{d}\right)$ 这玩意儿单独拿出来，$O(nH(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
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const LL MOD = 1e9+7;
const int N = 200005;
int mu[N], pList[N], pID;
bool notP[N];
void Euler(int n){
notP[0] = notP[1] = 1;
mu[1] = 1;
for(int i = 1; i <= n; i++){
if(notP[i] == 0){
pList[++pID] = i;
mu[i] = -1;
}
for(int j = 1; j <= pID; j++){
if(1ll * i * pList[j] > n) break;
notP[i * pList[j]] = 1;
if(i % pList[j] == 0){
mu[i * pList[j]] = 0;
break;
}
else mu[i * pList[j]] = -mu[i];
}
}
}
inline LL fpow(LL bs, LL idx){
LL res = 1;
bs %= MOD;
while(idx){
if(idx & 1) (res *= bs) %= MOD;
(bs *= bs) %= MOD;
idx >>= 1;
}
return res;
}
int T;
LL k, x;
LL f[N], S[N], inv, g[N];
int main(){
Euler(200000);
read(T, k, x);
for(int d = 1; d <= 200000; d++)
for(int i = d; i <= 200000; i += d)
(f[i] += d * mu[d] % MOD * mu[d] % MOD * mu[i / d] % MOD) %= MOD;
for(int i = 1; i <= 200000; i++){
S[i] = (S[i-1] + fpow(i, k * x % (MOD-1)) * f[i] % MOD) % MOD;
g[i] = (g[i-1] + fpow(i, k)) % MOD;
}
while(T--){
LL ans = 0;
LL n; read(n);
for(LL l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
ans += ((S[r] - S[l-1]) % MOD + MOD) * fpow(g[n/l], x) % MOD;
ans %= MOD;
}
printf("%lld\n", ans);
}
return 0;
}
|
1009 Divisibility
真是巧了，前几天才看了这个问题。
根据九余数定理的推广，一个 $b$ 进制数的各个数位相加与它本身模 $x$ 同余的充要条件是：$b\equiv1\pmod x$.
所以这道题只需要判断是否 $b\bmod x=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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T;
LL b, x;
int main(){
for(read(T); T; T--){
read(b, x);
if(b % x == 1) puts("T");
else puts("F");
}
return 0;
}
|
1010 Expectation
对每一位运用 $\textbf{Matrix-Tree Theorem}$ 计算这一位的生成树数量，这些数量按照二进制乘出来之后除以总的生成树数量即可。
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 105;
const int M = 20005;
const LL MOD = 998244353;
inline LL fpow(LL bs, LL idx){
bs %= MOD;
LL res = 1;
while(idx){
if(idx & 1) (res *= bs) %= MOD;
(bs *= bs) %= MOD;
idx >>= 1;
}
return res;
}
namespace LA{
int n;
LL a[N][N], b[N];
void init(int nn){
n = nn;
for(int i = 1; i <= n; i++){
b[i] = 0;
for(int j = 0; j <= n; j++) a[i][j] = 0;
}
}
LL det(){
LL res = 1;
int flag = 1;
for(int j = 1; j <= n; j++){
int r = j;
for(int i = j + 1; i <= n; i++)
if(a[i][j] > a[j][j])
r = i;
if(r != j) swap(a[r], a[j]), flag = -flag;
if(a[j][j] == 0) return 0;
for(int i = 1; i <= n; i++){
if(i == j) continue;
LL div = a[i][j] * fpow(a[j][j], MOD-2) % MOD;
for(int k = j; k <= n; k++){
a[i][k] -= div * a[j][k] % MOD;
((a[i][k] %= MOD) += MOD) %= MOD;
}
}
}
for(int i = 1; i <= n; i++) (res *= a[i][i]) %= MOD;
return flag > 0 ? res : MOD - res;
}
}
int T, n, m;
LL u[M], v[M], w[M];
inline LL solve(int b){
LA::init(n-1);
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
LA::a[i][j] = 0;
for(int i = 1; i <= m; i++){
if(b == -1 || ((w[i] >> b) & 1)){
LA::a[u[i]][v[i]]--, LA::a[v[i]][u[i]]--;
LA::a[u[i]][u[i]]++, LA::a[v[i]][v[i]]++;
}
}
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
((LA::a[i][j] %= MOD) += MOD) %= MOD;
return LA::det();
}
int main(){
for(read(T); T; T--){
read(n, m);
for(int i = 1; i <= m; i++) read(u[i], v[i], w[i]);
LL ans = 0;
for(int b = 31; b >= 0; b--) ans = (ans * 2 + solve(b)) % MOD;
LL tot = solve(-1);
printf("%lld\n", ans * fpow(tot, MOD-2) % MOD);
}
return 0;
}
|