https://codeforces.com/contest/893/problem/E
C(n,m)不越界但A(n,m)越界的解决方案
C(n,m) = A(n,m) / (n-m)!
这题要模1e9+7,但是只有加减乘能模,除法模不了。所以这个A(n,m)要存原值,原值也太大了,爆 long long
要是能不要除法,全是乘法就好了文章来源:https://www.toymoban.com/news/detail-667401.html
法一:拆成多个质数相乘
先算A(n,m)里有多少个2 3 5 7,再减去(n-m)!中2 3 5 7的个数,最后把剩下的乘起来文章来源地址https://www.toymoban.com/news/detail-667401.html
long long C(int n, int m){
long long ret=1;
unordered_map<int,int> table;
for(int x=n;x>m;x--){
int tmpx=x;
for(int i=2;i<=tmpx;i++){
if(tmpx%i==0){
int tmpcnt=1;
tmpx=tmpx/i;
while(tmpx%i==0 && tmpx){
tmpcnt++;
tmpx/=i;
}
table[i]+=tmpcnt;
}
}
}
for(int x=n-m;x>=1;x--){
int tmpx=x;
for(int i=2;i<=tmpx;i++){
if(tmpx%i==0){
int tmpcnt=1;
tmpx=tmpx/i;
while(tmpx%i==0 && tmpx){
tmpcnt++;
tmpx/=i;
}
table[i]-=tmpcnt;
}
}
}
for(auto it=table.begin(); it!=table.end();it++){
int x=it->first;
int cnt=it->second;
到了这里,关于【算法随记】C(n,m)不越界但A(n,m)越界;的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!