本文主要是介绍xiaoxin juju needs help HDU - 5651，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
求组合数C(n,k) 的模一般有三种方法 杨辉三角预处理 卢卡斯定理 还有费马小定理
在杨辉三角中有公式 C(n,k)=C(n-1,k)+C(n-1,k-1) 适用于n与k都不太大时 可以用二维数组保存
卢卡斯定理用来求 C(n,k)%p 其中p为素数 有公式C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
费马小定理是利用乘法逆元来求组合数 对于素数p有 (a^(p-1))%p=1 则a的乘法逆元则为a^(p-2) 因此C(n,k)= ( n!%p * (((n-k)!)^(p-2))%p * ((k!)^(p-2))%p )%p
费马小定理求解
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007ll pre[1010];
int book[100];void init()
{ll i;pre[0]=1;for(i=1;i<=1000;i++){pre[i]=((pre[i-1]%M)*i)%M;}return;
}ll quickmod(ll a,ll b)
{ll sum;sum=1;while(b>0){if(b%2==1){sum=((sum%M)*(a%M))%M;}a=((a%M)*(a%M))%M;b/=2;}return sum;
}ll getres(ll n,ll k)
{ll sum;sum=((((pre[n]%M)*(quickmod(pre[n-k],M-2)%M))%M)*(quickmod(pre[k],M-2)%M))%M;return sum;
}int main()
{ll sum;int t,n,i,cnt;char ch[1010];init();scanf("%d",&t);while(t--){scanf("%s",ch);memset(book,0,sizeof(book));n=strlen(ch);for(i=0;i<n;i++){book[ch[i]-'a']++;}cnt=0;for(i=0;i<52;i++){if(book[i]%2==1) cnt++;book[i]/=2;}if(cnt>1){printf("0\n");continue;}n/=2;sum=1;for(i=0;i<52;i++){if(book[i]>0){sum=((sum%M)*(getres(n,book[i])%M))%M;n-=book[i];}if(n==0) break;}printf("%lld\n",sum);}return 0;
}
杨辉三角预处理求解
#include <bits/stdc++.h> using namespace std; #define M 1000000007 #define ll long long
ll c[510][510];
void init() { int i,j; for(i=0;i<=500;i++) { c[i][0]=1; c[i][i]=1; } for(i=1;i<=500;i++) { for(j=1;j<=i-1;j++) { c[i][j]=(c[i-1][j]%M+c[i-1][j-1]%M)%M; } } return; }
int main() { ll sum; int book[26]; int t,n,i,cnt; char ch[1010]; init(); scanf("%d",&t); while(t--) { scanf("%s",ch); memset(book,0,sizeof(book)); n=strlen(ch); for(i=0;i<n;i++) { book[ch[i]-'a']++; } cnt=0; for(i=0;i<26;i++) { if(book[i]%2==1) cnt++; book[i]/=2; } if(cnt>1) { printf("0\n"); continue; } n/=2,sum=1; for(i=0;i<26;i++) { if(book[i]>0) { sum=(sum%M)*(c[n][book[i]]%M)%M; n-=book[i]; } if(n==0) break; } printf("%lld\n",sum); } return 0; }
这篇关于xiaoxin juju needs help HDU - 5651的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
