• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# AtCoder Beginner Contest 171 题解

4小时前 1次浏览

## A

``````#include<bits/stdc++.h>
using namespace std;

int main(){
char t; cin>>t;
putchar(islower(t)? 'a': 'A');
return 0;
}
``````

## B

``````#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int w[N];

int main(){
int n, k; cin>>n>>k;
for(int i=1; i<=n; i++) cin>>w[i];
sort(w+1, w+1+n);

int res=0;
for(int i=1; i<=k; i++) res+=w[i];
cout<<res;

return 0;
}
``````

## C

``````#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
ll n; cin>>n;
int stk[20]={0}, top=0;

while(n>0){
stk[++top]=n%26? n%26: 26;

bool ok=false;
if(n%26==0) ok=true;
n/=26; n-=ok;
}

for(int i=top; i; i--) cout<<(char)('a'+stk[i]-1);

return 0;
}
``````

## D

``````#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl 'n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}

const int N=1e5+5;

int n, q;
int cnt[N];
ll res;

int main(){
rep(i,1,n){
cnt[t]++; res+=t;
}

rep(i,1,q){
res+=cnt[a]*(b-a);
cnt[b]+=cnt[a];
cnt[a]=0;
cout<<res<<endl;
}

return 0;
}
``````

## E

``````#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl 'n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}

const int N=2e5+5;

int w[N], res[N], s;

int main(){

rep(i,1,n) res[i]=s^w[i];
rep(i,1,n) cout<<res[i]<<' ';

return 0;
}
``````

## F

### 分析

(s) 的长度为 (n)

(i) 右边的位置可以任意选择，方案数为 (26^{n+k-i})

(i) 位置对应的字母是 (s) 的结尾（也就是 (s)(n) 个字符）

(i) 左边，可以选出 (n-1) 个位置为 (s) 的前 (n-1) 个字符，方案数为 (C_{i-1}^{n-1}) ，剩下的位置方案数为 (25^{i-1-(n-1)}=25^{i-n}) 。（因为要保证第一个子序列的形态不重复）

``````#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl 'n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}

const int N=2e6+5, mod=1e9+7;

ll fpow(ll x,ll p)
{
ll res=1;
for(;p;p>>=1,x=x*x%mod)
if(p&1)res=res*x%mod;
return res%mod;
}

ll inv(ll x){
return fpow(x,mod-2)%mod;
}

ll fac[N];

void init(){
fac[0]=1;
for(int i=1; i<N; i++) fac[i]=fac[i-1]*i%mod;
}

ll C(ll a, ll b){
return fac[a]*inv(fac[b])%mod*inv(fac[a-b])%mod;
}

int main(){
init();
int k; string s; cin>>k>>s;
int n=s.size();

ll res=0;
rep(i,n,n+k) res=(res+C(i-1, n-1)*fpow(25, i-n)%mod*fpow(26, n+k-i))%mod;
cout<<res;

return 0;
}
``````