ACdream1139 Sum(推公式+逆元求解) - c++编程基础

TOP

ACdream1139 Sum(推公式+逆元求解)

2015-11-21 01:00:33 来源: 作者: 【大中小】浏览:2次

Tags：ACdream1139 Sum 公式求解

题意：

给定一个由0~9组成的矩阵，我们求行相邻的组成的数与列相邻的组成的数的和。

eg:

123

456

789

第一行组成的数有 1,2,3,12，23,123

第一列组成的数有 1,4,7,12,47,147.

暴力枚举所有的数肯定是不可取的，我们试着总结。

我们发现a[x][y]在行里出现的数对以后和的贡献为 x*a[x][y]sigma(10 ^（n-i）) (k<=x<=n)

同理a[x][y]在列里出现的数对以后和的贡献为 y*a[x][y]sigma(10 ^（n-i）) (y<=x<=n)

我们设sum[x]表示第x行与第x列的数的和然后对以上的公式进行合并

sum = sigma( i * sum[i] * ( sigma(10^k)(i<=k<=n)))(1<=i<=n)

sigma(10^k)(i<=k<=n)用到等比数列求和，有除法，需要用到逆元

a/b (mod c) == a (mod b*c)/c

或者 a*~b (mod c)

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include
         #include 
         
           #define PB push_back #define MP make_pair #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,l,h) for(int i=(l);i<=(h);++i) #define DWN(i,h,l) for(int i=(h);i>=(l);--i) #define IFOR(i,h,l,v) for(int i=(h);i<=(l);i+=(v)) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define MAX3(a,b,c) max(a,max(b,c)) #define MAX4(a,b,c,d) max(max(a,b),max(c,d)) #define MIN3(a,b,c) min(a,min(b,c)) #define MIN4(a,b,c,d) min(min(a,b),min(c,d)) #define PI acos(-1.0) #define INF 1000000000 #define LINF 1000000000000000000LL #define eps 1e-8 #define LL long long using namespace std; const int maxn = 1010; const LL mod = 1e9+7; char a[maxn][maxn]; LL sum[maxn]; LL multi(LL a,LL b){ LL ans = 0; while(b){ if(b&1) ans=(ans+a)%mod; b>>=1; a=(a+a)%mod; } return ans; } LL quick_mod(LL a,LL b){ LL ans = 1; while(b){ if(b&1) ans=multi(ans,a); b>>=1; a=multi(a,a); } return ans; } int main() { int n; while(~scanf(%d,&n)){ REP(i,n) scanf(%s,a[i]); CLR(sum); REP(i,n) REP(j,n) sum[i]=sum[i]+a[j][i]-'0'+a[i][j]-'0'; LL ans=0; LL M = quick_mod(9LL,mod-2); REP(i,n){ LL t = (quick_mod(10,n-i)+mod-1)%mod; t=multi(t,M); t=multi(sum[i],t); ans=(ans+multi(i+1,t))%mod; } printf(%lld ,ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：LeetCode 7: Reverse Integer	下一篇：hdu 3658(矩阵快速幂)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: