2 条题解
-
0
设 为 数列的前缀和,那么题目给出的方程可统统化为如下形式:
联立相邻的两方程:
$$x_{i+1}p_{i+1}+y_{i+1}p_n-y_{i+1}p_{i}\equiv z_{i+1}\pmod {10^9+7} $$借用上面的方程,消掉下面的方程中 项。
消完之后运用最后一个方程解出 的值,一路往上回代即可。
无解和多解,考虑最后一个方程被消元后的结果:
当 且 时, 有 个解。
当 且 时, 有 个解。
这玩意时间复杂度是 的,实现的不精细是 的
void solve() { n=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),z[i]=read(); if(n==1) { if(add(x[1],y[1])==0) { if(z[1]==0) write(mod); else write(0); enter; return; } write(1),enter; write(1ll*z[1]*fpow(add(x[1],y[1]),mod-2)%mod);enter; return; } for(int i=2;i<n;i++) { int tmp=1ll*y[i]*fpow(x[i-1],mod-2)%mod; y[i]=add(1ll*y[i-1]*tmp%mod,y[i]); z[i]=add(1ll*z[i-1]*tmp%mod,z[i]); } int tmp1=add(x[n],add(y[n],1ll*y[n-1]*y[n]%mod*fpow(x[n-1],mod-2)%mod)); int tmp2=add(z[n],1ll*z[n-1]*y[n]%mod*fpow(x[n-1],mod-2)%mod); if(tmp1==0) { if(tmp2==0) write(mod); else write(0); enter;return; } pre[n]=1ll*tmp2*fpow(tmp1,mod-2)%mod; for(int i=1;i<n;i++) pre[i]=1ll*del(z[i],1ll*y[i]*pre[n]%mod)*fpow(x[i],mod-2)%mod; write(1),enter; for(int i=1;i<=n;i++) write(del(pre[i],pre[i-1])),space; enter; }
-
-3
#define int long long const int MAXN = 2e5 + 10, mod = 1e9 + 7; inline int power(int x, int k) { int ret = 1; while(k) { if(k & 1) ret = ret * x % mod; x = x * x % mod; k >>= 1; } return ret; } inline int inv(int x) {return power(x, mod - 2);} int T, n; int x[MAXN], y[MAXN], z[MAXN]; int a[MAXN], b[MAXN], c[MAXN]; int s[MAXN]; signed main() { T = read(); while(T--) { n = read(); for(int i = 1; i <= n; i++) { x[i] = read(); y[i] = read(); z[i] = read(); } //对每个x,y,z,x[i]s[i] - y[i]s[i-1] + y[i]s[n] = z[i] for(int i = 1; i < n; i++) {//高斯消元解前缀和 a[i] = mod - y[i]; b[i] = x[i]; c[i] = y[i]; } a[n] = mod - y[n]; c[n] = (x[n] + y[n]) % mod; for(int i = 1; i < n; i++) {//用第i行消掉第i+1行的第i列 int k = a[i + 1] * inv(b[i]) % mod; (a[i + 1] -= k * b[i] % mod) %= mod; (c[i + 1] -= k * c[i] % mod) %= mod; (z[i + 1] -= k * z[i] % mod) %= mod; } int roots = 1; if(c[n] == 0 && z[n] != 0) { putchar('0'); putchar('\n'); continue; } else if(c[n] == 0 && z[n] == 0) roots = mod; else s[n] = z[n] * inv(c[n]) % mod; for(int i = 1; i <= n - 1; i++) { int right = (z[i] - c[i] * s[n] % mod) % mod; if(b[i] == 0 && right != 0) {roots = 0; break;} else if(b[i] == 0 && right == 0) roots += mod; else s[i] = ((z[i] - c[i] * s[n] % mod) * inv(b[i]) % mod + mod) % mod; } if(roots != 1) {printf("%lld\n", roots); continue;} else {putchar('1'); putchar('\n');} for(int i = 1; i <= n; i++) printf("%lld ", ((s[i] - s[i - 1]) % mod + mod) % mod); putchar('\n'); } return 0; }
- 1
信息
- ID
- 208
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 258
- 已通过
- 17
- 上传者