AtCoder Beginner Contest 171 F.Strivore 【数论|AtCoder Beginner Contest 171 F.Strivore】题目链接
文章图片
简单的组合数学~
我们首先可以确实最终的字符串有几个字符，那么我们每次可以挑i i i 个位置，答案即为C s u m i C_{sum}^i Csumi?，那对这i i i 个位置，每个位置都有25 25 25 个选择，答案即为2 5 i 25^i 25i，两个相乘即可，AC代码如下：
#include
using namespace std;
typedef long long ll;
const int N=2e6+5;
const ll mod=1e9+7;
ll F[N],I[N];
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;
}
ll f(ll a,ll b)//快速乘
{
ll k=0;
while(b)
{
if(b&1) k=(k+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return k;
}void init(){//预处理算组合数
F[0]=1;
ll s=1;
for(int i=1;
i<=N;
i++){
s=f(s,i);
F[i]=s;
}
I[N]=power(F[N],mod-2);
for(int i=N;
i--;
){
I[i]=f(I[i+1],i+1);
}
}ll C(ll n, ll k){
return f(f(F[n],I[n-k]),I[k]);
}main(){
init();
ll k;
string s;
cin>>k>>s;
ll len=s.size(),sum=k+len,ans=0;
for(ll i=len;
i<=sum;
i++) ans=(ans+C(sum,i)*power(25,sum-i))%mod;
cout< 推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组