训练情况
赛后反思
组合数学还得加练，J题奇妙的乘法逆元预处理，开个unordered_map记忆化就过了？！，E题太头铁了，异或不算就直接交，F题又是急到没取模就直接交。
A题
字符串 Tomori 后面补上 Haruhikage。
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
void solve(){
string s; cin>>s;
cout<<s<<endl;
if(s == "Tomori") cout<<"Haruhikage"<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
N题
找票数最多的人的名字
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
string ans;
int now;
void solve(){
string s; cin>>s;
int x; cin>>x;
if(x > now){
now = x;
ans = s;
}
}
signed main(){
int T; cin>>T; while(T--)
solve();
cout<<ans<<endl;
return 0;
}
F题
由于这题保证字符串之间互不相同，所以它下面给的字符串并没有什么用，所以只需要 \(n\) 就可以计算答案，对于某一种缩写，对答案的贡献就是它的全排列，就是从 \(n\) 个字符串里面选 \(1,2,3,4,\cdots,n\) 的全排列，所以这题的答案是 \(A_n^1 + A_n^2 + A_n^3 \cdots A_n^n\)。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7;
void solve(){
int n; cin>>n;
int ans = 0;
int now = 1;
for(int i = n;i;i--){
now *= i;
now %= mod;
ans += now;
ans %= mod;
}
cout<<ans<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
I题
\(i\) 可以跳到 \(a_i\)，对于两个不互通的环，我们需要交换两个环上的任意元素即可打通，所以最后需要交换的次数就是不同环的个数-1，所以我们直接并查集（DSU）维护，最后求有多少个不同的环，答案再减一。
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 3;
int fa[N];
int Find(int x){
if(fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
void Union(int x,int y){
x = Find(x); y = Find(y);
if(x == y) return;
fa[y] = x;
}
void solve(){
int n; cin>>n;
vector<int> a(n + 1);
for(int i = 1;i<=n;i++) fa[i] = i,cin>>a[i];
for(int i = 1;i<=n;i++){
Union(i,a[i]);
}
vector<bool> vis(n + 1);
int ans = 0;
for(int i = 1;i<=n;i++){
if(!vis[Find(i)]){
vis[Find(i)] = 1;
ans++;
}
}
cout<<ans-1<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
E题
我们观察发现每一行每一列上的元素都互不相同才能让异或最小
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int N = 507;
int n;
int a[N][N];
void solve(){
cin>>n;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
a[i][j] = (i+j)%n;
}
}
int ans = 0;
for(int i = 0;i<n;i++) ans^=(i+1);
cout<<ans<<endl;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
cout<<a[i][j]+1<<" ";
}
cout<<endl;
}
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
J题
赢 \(n\) 次，输 \(n-1\) 次，输的位置可以在任意位置，有 \(C_{n+k-1}^k\) 种，由于是独立事件，概率就是每个事件概率的乘积，所以答案就是
\[\sum_{i=0}^{n-1}p^n \times (1-p)^i \times C_{n+k-1}^k \]#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 3;
int jc[N];
inline int read(){
int s = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
s = (s << 1) + (s << 3) + (c ^ 48);
c = getchar();
}
return s;
}
void print(int x){
if(x > 9) print(x/10);
putchar(x%10+48);
}
int ksm(int a,int b){
int x = a;
int y = b;
int ans = 1;
while(y){
if(y&1){
ans *= x;
ans %= mod;
}
x*=x;
x%=mod;
y>>=1;
}
return ans;
}
unordered_map<int,int> pinv;
int inv(int x){
if(pinv[x]) return pinv[x];
return pinv[x] = ksm(x,mod-2);
}
void pre(){
jc[0] = 1;
for(int i = 1;i<=N-3;i++) jc[i] = jc[i-1]*i,jc[i] %= mod;
}
int C(int n,int m){
return (((jc[n]*inv(jc[n-m])) % mod)*inv(jc[m])) % mod;
}
void solve(){
int n,p,q; n = read(); p = read(); q = read();
int win = (p*inv(q)) % mod;
int lose = ((q-p)*inv(q)) % mod;
int powwin = ksm(win,n);
int powlose = 1;
int ans = 0;
for(int k = 0;k<=n-1;k++){
ans += (((powwin*powlose) % mod)*C(n+k-1,k)) % mod;
powlose *= lose; powlose%=mod;
ans %= mod;
}
print(ans); puts("");
}
signed main(){
pre();
int T; T = read(); while(T--)
solve();
return 0;
}