首页 > 代码库 > 求第n行杨辉三角(n很大,取模
求第n行杨辉三角(n很大,取模
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 typedef long long ll; 6 const int maxn=1000; 7 ll mod;int n; 8 ll c[100000],A[100000]; 9 void init(){ 10 A[1]=1; 11 ll p=mod; 12 //线性求逆元 13 for(int i=2;i<=n;++i){ 14 A[i] = ((p-(p / i)) * A[p % i]%p+p)%p; 15 } 16 c[0]=1; 17 printf("1->"); 18 for(int i=1;i<=n;++i){ 19 //先c[i-1]*(n-i+1),否则c[i-1]可能不整除i 20 c[i]=(((c[i-1]*(n-i+1)%p)*A[i]))%p; 21 printf("%lld->",c[i]); 22 } 23 printf("\n"); 24 } 25 int main(){ 26 while(~scanf("%d",&n)){ 27 mod=1e9+7; 28 init(); 29 } 30 return 0; 31 }
为什么不能算出来取模而用逆元呢
因为我们还要通过该结果递推其他的项,直接取模可能造成后面的数不整除前面的项
如果只算一项,取模是可以的
或者只取模一次,那么可以直接对结果取模
算逆元时一定要考虑式子对逆元的整除性
求第n行杨辉三角(n很大,取模
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。