目录
7.21 2020 Multi-University Training Contest 1题解及补题
比赛过程
深深的见识到了，妥妥的难，emm，只有了思维的D签到。
题解
D Distinct Sub-palindromes
题意
给你一个长度n，你需要找出来一些串，这些串由A...Z和a...z构成。我们设长度为n的所有串中所包含回文子串最少的数量为ans。问你长度为n，且包含回文子串数量为ans的串有多少种。例如“aaaa” 的回文子串有 “a”, “aa”, “aaa” and “aaaa”.
解法
n=1和 n=2的答案都已给出。n=3的时候 abc型、aab型、aaa型中所包含子回文串数量都一样是最少的，所以n=3时候答案是26×26×26。之后就是找规律，这里直接说答案，如果一个串是abcabcabc……这样的串，它的回文串数量最少。那么n>3之后的答案就是26×25×24
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
if(n==1){
printf("%d\n",26);
}
else if(n==2){
printf("%d\n",676);
}
else if(n==3){
printf("%d\n",17576);
}
else{
printf("%d\n",15600);
}
}
}
E Fibonacci Sum
题意
给你\(n，c，k(1 <= n, c <= 10^{18}, 1 <= k <= 10^{15})\)，求\(\sum_{i = 1}^{n}{ (F_{ic})^k} \,mod (10^{9} + 9)\),其中\(F\)表示斐波那契数列
解法
根据斐波那契数列的通项公式我们可以得到
\[\sum_{i = 1}^{n}{ (F_{ic})^k} = (\frac{1}{\sqrt{5}})^k\sum_{i = 1}^{n}[(\frac{1 + \sqrt{5}}{2}) ^ {ic} - (\frac{1 - \sqrt{5}}{2}) ^ {ic}] ^ k \]
令\(\,p = \frac{1}{\sqrt{5}}, A = \frac{1 + \sqrt{5}}{2}, B = \frac{1 - \sqrt{5}}{2}\)，则
\[\sum_{i = 1}^{n}{ (F_{ic})^k} = (p)^k\sum_{i = 1}^{n}(A ^ {ic}-B ^ {ic}) ^ k \]
将\((A ^ {ic}-B ^ {ic}) ^ k\)展开，得到
\[\sum_{i = 1}^{n}{ (F_{ic})^k} = (p)^k\sum_{i = 1}^{n}(A ^ {ic}-B ^ {ic}) ^ k = (p)^k\sum_{i = 1}^{n}\sum_{j = 0}^{k}(-1)^{k-j}C_k^jA^{icj}B^{ic(k-j)} \]
将 j 相同的\(A^{icj}B^{ic(k-j)}\)合并，即
\[(p)^k\sum_{i = 1}^{n}\sum_{j = 0}^{k}(-1)^{k-j}C_k^jA^{icj}B^{ic(k-j)} = (p)^k\sum_{j = 0}^{k}[(-1)^{k-j}C_k^j\sum_{i = 1}^{n}(A^{cj}B^{c(k-j)})^i] \]
我们发现\(\sum_{i = 1}^{n}(A^{cj}B^{c(k-j)})^i\)实际是一个首项公比都为\(A^{cj}B^{c(k-j)}\)，设\(q = A^{cj}B^{c(k-j)}\), 则\(\sum_{i = 1}^{n}(A^{cj}B^{c(k-j)})^i = \frac{q(q^n - 1)}{q - 1}\)，所以
\[\sum_{i = 1}^{n}{ (F_{ic})^k} = (p)^k\sum_{j = 0}^{k}[(-1)^{k-j}C_k^j\frac{q(q^n - 1)}{q - 1}] \]
并且，\(\sqrt{5}\)可以用5在模1e9+9的二次剩余383008016替代（\({383008016}^2\equiv 5 \,(mod \,{10}^9 + 9)\)）。
优化：
1）因为\(p = 10^{9} + 9\)是质数，所以对任意x，\(gcd(x, p) = 1\),所以根据欧拉降幂公式，\(a ^ b \% p = a ^ {b \% (p - 1)} \% p\)，利用这个原理对幂较大的进行降幂。
2）在求q的值的时候，求出 j = 0 时，即\(B^{ck}\),之后再乘上\(\frac{a^c}{b^c}\),即可得到 j = 1 时q的值。
代码
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = ~0u >> 1;
const ll mod = 1e9 + 9;
typedef pair<int,int> P;
#define REP(i, a, n) for (int i = a; i < (n); ++i)
#define PER(i, a, n) for (int i = (n) - 1; i >= a; --i)
const int A = 691504013; // (1 + sqrt(5)) / 2
const int B = 308495997; // (1 - sqrt(5)) / 2
const int C = 276601605; // 1 / sqrt(5)
ll n, c, k;
ll f[maxn]; // f[x] = x!
ll g[maxn]; // g[x] = x! ^ (-1)
ll r[maxn]; // r[x] = x ^ (-1)
void init() {
f[0] = g[0] = f[1] = g[1] = r[1] = 1;
for (int i = 2; i < maxn; i++) {
f[i] = (long long)f[i - 1] * i % mod;
r[i] = (long long)(mod - mod / i) * r[mod % i] % mod;
g[i] = (long long)g[i - 1] * r[i] % mod;
}
}
inline int nCm(int n, int m) {
if (m < 0 || m > n) return 0;
return (long long)f[n] * g[m] % mod * g[n - m] % mod;
}
inline ll qpowmod(ll a, ll b, ll p) {
a %= p;
ll ans = 1, base = a;
while (b) {
if (b & 1) {
ans = (ans * base) % p;
}
base = base * base % p;
b >>= 1;
}
return ans;
}
int main() {
IO;
init();
int t;
cin >> t;
while (t--) {
cin >> n >> c >> k;
ll A_c = qpowmod(A, c % (mod - 1), mod);// (1 + sqrt(5)) / 2 的 c次方
ll B_c = qpowmod(B, c % (mod - 1), mod);// (1 - sqrt(5)) / 2 的 c次方
ll q = qpowmod(B_c, k, mod); //(1 - sqrt(5)) / 2 的 c次方 的 k次方
ll B_c_inv = qpowmod(B_c, mod - 2, mod);// (1 - sqrt(5)) / 2 的 c次方 的逆元
ll d = A_c * B_c_inv % mod;
ll ans = 0;
REP(i, 0, k + 1) {
ll temp;
if (q == 1)
temp = n % mod;
else
temp = q * (qpowmod(q, n % (mod - 1), mod) - 1 + mod) % mod * qpowmod(q - 1, mod - 2, mod) % mod;
temp = temp * nCm(k, i) % mod;
if ((k - i) & 1) {
ans = (ans - temp + mod) % mod;
}
else {
ans = (ans + temp) % mod;
}
q = q * d % mod;
}
cout << ans * qpowmod(C, k, mod) % mod << endl;
}
return 0;
}
F
题意
解法
代码
//将内容替换成代码
I Leading Robots
题意
T组输入
然后给您n个机器人的初始位置p和加速度a，问你有多少个机器人会出现领先于其他所有机器人的情况（注意是领先于其他所有）也就是说并行的两个是不可能出现领先的情况的。
解法
首先，我们很容易知道一个点能当第一的条件是它在超过前面所有人之前不能被他后面的人超过。那么先考虑哪些点能超过前面的所有点呢？显然需要你的加速度大于前面所有点的加速度，那么我们就可以先按照位置排序，再按照加速度排，只考虑 \(pos1>pos2 \,\&\& \,a1<a2\) 的点即可。
我们处理出这些点以后应该怎么办呢？朴素想法：枚举上述处理后的每个点，计算自己成为第一的时间t1，再计算后面的点超过自己最短的时间t2，若t1<t2，则会对答案产生贡献。思路很清晰，但是总复杂度为O(n^2)。
其实在计算过程中就能意识到这里面由很多无用的计算，比如，我已经知道点3能在点2超过点1之前超过点1，也知道点4不能在点2超过点1之前超过点1，那么我就没必要去计算点3、点4谁能先超过点2，我个人觉得这个逻辑还是比较好理解的。但是在朴素算法中这些无用的计算都存在。那么我们应该怎样取优化它呢？
优化算法：利用栈后进先出的性质，对n从前往后枚举，每次比较时取栈顶两个点u1、u2，若 t（u1->u2）<t（i ->u2）则说明当前点i不能在u1到达u2前到达u2，因此push(i)，点i成为新的栈顶；若 t（u1->u2）>=t（i ->u2）则说明当前点i能在u1到达u2前到达u2，因此pop(u1)，因为u1能被点i超过，不可能成为第一，然后对栈内元素继续如上所述操作下去。
代码
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
using namespace std;
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int inf = 0x3f3f3f3f;
typedef long long ll;
const int maxn = 100500;
const ll mod = 1e9 + 7;
typedef pair<int,int> pii;
const double pi = acos(-1);
int n,m;
struct node{
ll p,a;
int vis;
}r[maxn],R[maxn];
bool cmp(node aa,node bb){
if(aa.p!=bb.p)return aa.p>bb.p;
else return aa.a>bb.a;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld %lld",&r[i].p,&r[i].a);
sort(r+1,r+n+1,cmp);
int cnt=0;
for(int i=1;i<=n;i++){
if(R[cnt].a==r[i].a&&R[cnt].p==r[i].p)R[cnt].vis=1;
if(R[cnt].a<r[i].a){
cnt++;
R[cnt].a=r[i].a;
R[cnt].p=r[i].p;
R[cnt].vis=0;
}
}
n=cnt;
stack<node>st;
st.push(R[1]);
if(n>1)st.push(R[2]);
for(int i=3;i<=n;i++){
while(st.size()>=2){
node u2=st.top();st.pop();
node u1=st.top();
ll t1=(u1.p-R[i].p)*(u2.a-u1.a);
ll t2=(u1.p-u2.p)*(R[i].a-u1.a);
if(t1>t2){
st.push(u2);
break;
}
}
st.push(R[i]);
}
int ans=0;
while(!st.empty()){
node u=st.top();st.pop();
ans+=(u.vis^1);
}
cout<<ans<<endl;
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--) solve();
}