XTU 1260 - Determinant - [2017湘潭邀请赛A题(江苏省赛)][高斯消元法][快速幂和逆元]

是2017江苏省赛的第一题，当时在场上没做出来（废话，那个时候又不懂高斯消元怎么写……而且数论也学得一塌糊涂，现在回来补了）

省赛结束之后，题解pdf就出来了，一看题解，嗯……加一行再求逆矩阵从而得到伴随矩阵从而得到答案，emmmmm真是非常通俗易懂呢！

于是在回学校的路上强行回忆上学期学的线性代数，把这题题解的原理想通了，然后到现在把高斯消元法补了，才把这题做出来……

 #include<cstdio>

 #include<algorithm>

 #define MAXN 205

 #define MOD 1000000007

 typedef long long ll;

 using namespace std;

 int n;

 ll a[MAXN][*MAXN],det;//注意矩阵的列数要是MAXN的两倍，因为( A , E ) -> ( E , inv(A) )

 ll pow(ll a,ll b){//快速幂

     ll r=,base=a%MOD;

     while(b){

         if(b&) r*=base , r%=MOD;

         base*=base;

         base%=MOD;

         b>>=;

     }

     return r;

 }

 ll inv_(ll a){return pow(a,MOD-);}//求逆元

 void debug()

 {

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=*n;j++) printf("%I64d ",a[i][j]);

         printf("\n");

     }

 }

 int Gauss_eli(int row,int col)

 {

     det=;

     for(int i=;i<=row;i++)//a[i][i]

     {

         int tmp;

         for(tmp=i;tmp<=n;tmp++) if(a[tmp][i]) break;

         if(tmp!=i) det*=-;//行列式交换两行要取负

         for(int j=;j<=col;j++) swap(a[tmp][j],a[i][j]);//交换两行

         det=(det*a[i][i]%MOD + MOD)%MOD;

         ll inv=inv_(a[i][i]);//求得逆元

         for(int j=;j<=col;j++) a[i][j]=a[i][j]*inv%MOD;

         for(int r=;r<=row;r++)

         {

             if(r==i) continue;

             ll mult=a[r][i];

             for(int c=;c<=col;c++) a[r][c]=(a[r][c] - a[i][c]*mult%MOD + MOD)%MOD;//消元

         }

         //debug(); printf("det = %I64d\n",det);

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output1.txt","w",stdout);

     while(scanf("%d",&n)!=EOF)

     {

         for(int j=;j<=n;j++) a[][j]=;

         for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%lld",&a[i][j]);

         for(int i=;i<=n;i++) for(int j=n+;j<=*n;j++) a[i][j]=(i==(j-n));

         Gauss_eli(n,*n);

         for(int i=;i<=n;i++)

         {

             if(i!=) printf(" ");

             if(i%==) a[i][n+]=(MOD - a[i][n+])%MOD;

             printf("%I64d",(a[i][n+]*det + MOD)%MOD);

         }

         printf("\n");

     }

 }

可以说是学到了，对高斯消元、逆元、取模等一系列问题有了更深的认识吧。

关于快速幂：

a^b，把b个a进行两两分组，比如：a*a*a*a*a*a => (a*a)*(a*a)*(a*a)

这样变的好处是，你只需要计算一次a*a，然后将结果(a*a)连乘自己两次就能得到a^6，即(a*a)^3=a^6。算一下发现这次一共乘了3次，少于原来的5次。

核心代码是：

 while(n)

 {

     if(n&) res=res*a;

     n>>=;

     a=a*a;

 }

完整版是：

 ll fpow(ll a,ll b){//快速幂

     ll r=,base=a%MOD;

     while(b){

         if(b&) r*=base , r%=MOD;

         base*=base;

         base%=MOD;

         b>>=;

     }

     return r;

 }

 ll fpow(ll a,ll i){//递归版快速幂

 　　if (i==) return ;

 　　int temp=pow(a,i>>);

 　　temp=temp*temp%MOD;

 　　if (i&) temp=(ll)temp*a%MOD;

 　　return temp%MOD;

 }

另附一个数据生成器，以后应该经常用得到……

 #include<cstdio>

 #include<cstdlib>

 #include<ctime>

 int get_rand(int m,int n)//[m,n]

 {

     return( rand()%(n - m + ) + m );

 }

 int main()

 {

     freopen("input.txt","w",stdout);

     srand(time(NULL));

     int n=get_rand(,);

     printf("%d\n",n);

     for(int i=;i<n;i++)

     {

         for(int j=;j<=n;j++) printf("%d ",get_rand(,));

         printf("\n");

     }

 }

巴特西

XTU 1260 - Determinant - [2017湘潭邀请赛A题(江苏省赛)][高斯消元法][快速幂和逆元]

最新文章

热门文章