近期训练题目思维整理(6.1)
2019 福建省赛 题目A
·题意
计算
其中，(p)为质数，(nle10^9)。
·思路
结论很简单，以下式子成立$$sum_{x=1}{p}xjmod{p}=0$$
那么我们只要求最后3项就可以获得答案
这个结论可以依靠打表获得，比赛时很多队依靠打表发现了结论轻松的过了这题，而我们的电脑空闲长达1个小时却没有尝试打表。对于一些没有思路的题目不妨可以依靠这种方法寻找规律
2019 福建省赛 题目J
还没补，大概思路有，补完填坑
2019.5 FZU月赛 题目D
·题意
对于有根树T，定义$$f(T)=sum_{x,yin V(T)且xle y}dist(x,y)$$求(n)个节点的有根树T中，满足(f(T)_{max})和(f(T)_{min})的树分别有多少种。
·思路
考虑无根树，满足(f(T)_{max})的树一定是一条链，但是注意正链与反链相同，因此共有$$frac{1}{2}prod_{i=1}^{n}i$$种。
而满足(f(T)_{min})的树肯定是菊花树(一个点连着剩下(n-1)个点)，共有$$n$$种。
然后考虑有根情况，而对于有根树根不同树便不同。因为n个点每个点都可以作为根，因此有根树的数量就是无根树的数量乘以(n)。
因此，结论:
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll inv = 5e8+4;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
ll n;
cin >> n;
ll ans1 = 0, ans2 = 0;
if(n == 1) ans1 = ans2 = 1;
else if(n == 2) ans1 = ans2 = 2;
else{
ans1 = 1, ans2 = (n*n)%mod;
for(ll i = 2;i <= n;i++)
ans1 = (ans1*i) % mod;
ans1 = ans1*n%mod*inv%mod;
}
cout << ans1 << ' ' << ans2 << endl;
return 0;
}
Codeforces 691E - Xor-sequences
·题意
长度为n的数组中选取k个数字组成序列x(可重复选取)，要求(x_{i}{oplus}x_{i+1})二进制下1的位数是3的倍数，求满足条件的数组的数量。
·思路
设二维数组(d_{i,j})保存序列({x_i,x_j})是否满足要求，满足要求为1不满足为0，二维数组(c_{i,j})保存的是某一长度下({x_i...y_i})(即以(x_i)为序列开头，(y_i)为序列结尾)的方案数。
很显然当长度为1时，(d_{i,j}=c_{i,j}).
那么长度为3时，二维数组(c_{i,j})所表示的意义(长度)可以由以下转移式转移：$$c_{i,j} = sum_{n}^{k=1}d_{i,k}d_{k,j}$$可以理解成枚举k,以i开头k结尾的序列和以k开头j结尾的序列拼接起来是否合法，有多少种合法方案累加起来。而这个公式就是矩阵乘法。
同理，当长度大于3时，$$c_{i,j} = sum_{n}^{k=1}c_{i,k}d_{k,j}$$，这样就可以使矩阵c的意义由(l-1)转移到(l)，那么转移到长度为k就要乘矩阵d共(k-1)次。
那么做法就很明显了，先预处理(d_{i,j})，而由于长度为2时(c_{i,j}=d_{i,j})，而我们要让矩阵c乘以矩阵d共(k-1)次，也就是d矩阵的(k-1)次幂。这题就转换成矩阵快速幂了。
·AC代码链接
Codeforces 691F - Couple Cover
·题意
从n个数字中取2个，得分为两个数字之积，当得分高于一个阈值p时获胜。给你m个数字p，问你以当前p为阈值时获胜的数字对的数量。
·思路
先预处理每个数字的数量，然后直接枚举数字{({i,j})}，计算有多少数字对可以凑成{(i*j)}，最后对数组求前缀和就可以计算失败的数字对。
这题直接枚举数字{({i,j})}复杂度是(n2)，而我们可以换个思路，由枚举{({i,j})}计算{({i*j})}转换为枚举{({i,i*j})}，因为阈值p是有上限的。这样枚举的复杂度就由(n2)转换为(nlog{n})。