这道题算是比较综合的了,要用到扩展欧几里得,乘法二分,高斯消元。
看了题解才做出来orz
基本思路是这样,建一个n*(n-1)的行列式,然后高斯消元。
关键就是在建行列式时会暴long long,所以要用取模来计算,即公式ax=b,等价于ax=b(mod p)
因为答案范围不超过正负10^17次,p可以取(2*10^17+3)。
然后加减乘除都能够进行了,乘法用乘法二分来做,除法用模线性方程求逆来做。
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL __int64
const LL p=(LL)200000000*1000000000+3;//杭电的编译器不能直接写200000000000000003,会ce
const LL L=(LL)100000000*1000000000;
LL ans[60],a[60][60],h[60][60];
int n;
LL modans(LL s)//取模
{
if(s<0)
s=s+p;
else if(s>=p)
s=s-p;
return s;
}
LL calcu(LL base,LL tmp)//乘法二分
{
LL ans=0;
while(tmp)
{
if(tmp&1)ans=modans(ans+base);
base=modans(base*2);
tmp/=2;
}
return ans;
}
void get_h(int s)//每一行初始化
{
int i,j;
LL tmp=0;
for(i=0;i<n;i++)
{
h[s][i]=modans(2*(a[s][i]-a[s+1][i]));
tmp+=calcu(a[s][i],a[s][i])-calcu(a[s+1][i],a[s+1][i]);
tmp=modans(tmp);
//printf("%I64d ",h[s][i]);
}
h[s][n]=tmp;
//printf("%I64d\n",h[s][n]);
}
void init()
{
int i,j;
for(i=0;i<n;i++)
get_h(i);
}
LL extEculid(LL a,LL b,LL &x,LL &y)
{
LL tmp,d;
if(b==0){x=1;y=0;return a;}
d=extEculid(b,a%b,x,y);
tmp=x;x=y;y=tmp-a/b*y;
return d;
}
void solve()
{
int i,j,k;
for(i=0;i<n;i++)//这一步不能落下,当第i行第i个数是0时,要与下面的行互换。这题数据貌似有点水,要是互换后第i个数还是0,就会出错了。。。
{
for(j=0;j<n;j++)
if(h[i][j])
break;
if(i<j)
{
for(k=0;k<=n;k++)
swap(h[i][k],h[j][k]);
}
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
int tmp=h[i][j];
for(k=i+1;k<=n;k++)
h[j][k]=modans(calcu(h[j][k],h[i][i])-calcu(h[i][k],h[j][i]));
}
}
LL x,y,g;
for(i=n-1;i>=0;i--)
{
g=extEculid(h[i][i],p,x,y);//由于p是质数,所以g实际上等于1
ans[i]=calcu(x,h[i][n]);
for(j=0;j<i;j++)
h[j][n]=modans(h[j][n]-calcu(h[j][i],ans[i]));
}
}
int main()
{
int t,i,j;
scanf("%d",&t);
for(int k=1;k<=t;k++)
{
scanf("%d",&n);
for(i=0;i<=n;i++)
for(j=0;j<n;j++)
{
scanf("%I64d",&a[i][j]);
a[i][j]+=L;
}
init();
solve();
printf("Case %d:\n",k);
printf("%I64d",(ans[0]-L)%L);
for(i=1;i<n;i++)
printf(" %I64d",(ans[i]-L)%L);
printf("\n");
}
return 0;
}
分享到:
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
杭电OnlineJudge 200-2099的解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
杭电ACM2000-2099题的解题报告
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh