程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ACdream1139 Sum(推公式+逆元求解)

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

編輯：C++入門知識

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;
}