2 solutions

  • 0
    @ 2021-10-5 17:21:13

    ppaa 数列的前缀和,那么题目给出的方程可统统化为如下形式:

    xipi+yipnyipi1zi(mod109+7)x_ip_i+y_ip_n-y_ip_{i-1}\equiv z_i\pmod {10^9+7}

    联立相邻的两方程:

    xipi+yipnyipi1zi(mod109+7)x_ip_i+y_ip_n-y_ip_{i-1}\equiv z_i\pmod {10^9+7}

    xi+1pi+1+yi+1pnyi+1pizi+1(mod109+7)x_{i+1}p_{i+1}+y_{i+1}p_n-y_{i+1}p_{i}\equiv z_{i+1}\pmod {10^9+7}

    借用上面的方程,消掉下面的方程中 yi+1pi-y_{i+1}p_i 项。

    消完之后运用最后一个方程解出 pnp_n 的值,一路往上回代即可。

    无解和多解,考虑最后一个方程被消元后的结果:

    ynpnzn(mod109+7)y_n'p_n\equiv z_n'\pmod {10^9+7}

    yn=0y'_n=0zn=0z'_n=0 时,pnp_n109+710^9+7 个解。

    yn=0y'_n=0zn0z'_n\not=0 时,pnp_n00 个解。

    这玩意时间复杂度是 O(n)O(n) 的,实现的不精细是 O(nlogmod)O(n\log \bmod)

    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;
    }
    
    • -1
      @ 2021-11-7 20:53:43

      #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

      Information

      ID
      208
      Time
      2000ms
      Memory
      512MiB
      Difficulty
      9
      Tags
      (None)
      # Submissions
      246
      Accepted
      16
      Uploaded By