2016年省赛H题目改编--H +模逆元

本文主要是介绍2016年省赛H题目改编--H +模逆元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Swap

Time Limit: 1 Sec		Memory Limit: 128 MB
Submit: 13		Solved: 2

Description

Input

Output

Sample Input

2
12
3
012
10
0123456789

Sample Output

45
369
555555115

Solution :

列举找规律+乘法逆元。举个列子吧。 12345 ，我们按照公式展开。得到

1 2 3 4 5

2 1 3 4 5

3 2 1 4 5

4 2 3 1 5

5 2 3 4 1

1 2 3 4 5 

1 3 2 4 5

1 4 3 2 5

1 5 3 4 2

1 2 3 4 5

1 2 4 3 5

1 2 5 4 3

1 2 3 4 5

1 2 3 5 4

1 2 3 4 5

转化一下就可以得到

得到n行

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

5 5 5 5 5

得到n*（n-1）/ 2行

1 2 3 4 5

。。。。

1 2 3 4 5

前面n行，每一行都提取一个 a（a就是当前行的数字），剩下一个等比数列

后面的行，单独计算每一行然后乘以n*（n-1）/ 2

注意：

等比数列求和得到的公式里面是（10^n-1）/ 9，先算上面，然后算下面，上面一定会先进行取模，那么下面就一定要求得9的模逆元才会使得最终答案是正确答案

即：9的逆元为num，那么最终答案是（（10^n-1）%mod * num） %mod

然后我的代码里面维护了一个10的指数的前缀

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

求两个互质元素的模逆元

LL qpowMod(LL m,LL n,LL p)
{LL ans=1;LL temp=m;while(n>0){if(n&1)ans=ans*temp%p;temp=temp*temp%p;n>>=1;}return ans;
}
LL getInverse(LL a,LL p)
{return qpowMod(a,p-2,p);
}

当a,m不是互质数，计算(b/a)mod m，没办法把b/a转换成b×（a的逆元），可以用  (b/a)mod m == [ b mod (a*m) ] / a 来代替

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define LL long long
#define MAXN 100005
const LL mod=1000000000+7;
char str[MAXN];
LL a[MAXN];
LL p[MAXN];void init()
{p[0]=1;for(int i=1;i<=MAXN;i++)p[i]=p[i-1]*10%mod;
}LL qpowMod(LL m,LL n,LL p)
{LL ans=1;LL temp=m;while(n>0){if(n&1)ans=ans*temp%p;temp=temp*temp%p;n>>=1;}return ans;
}
LL getInverse(LL a,LL p)
{return qpowMod(a,p-2,p);
}int main()
{LL n;init();LL num=getInverse(9,mod);//freopen("in.txt","r",stdin);while(scanf("%lld",&n)!=EOF){LL sum=0;scanf("%s",str);LL ans1=0,ans2=1;for(int i=0;i<n;i++){sum+=str[i]-'0';a[i]=str[i]-'0';ans1=(ans1*10+a[i])%mod;}ans1=(ans1*((n*(n-1)/2)%mod))%mod;ans2=((p[n]-1)*sum)%mod;ans2=(ans2*num)%mod;ans1=(ans1+ans2)%mod;printf("%lld\n",ans1);}return 0;
}

这篇关于2016年省赛H题目改编--H +模逆元的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---