結果

問題 No.426 往復漸化式
ユーザー ryofjt
提出日時 2016-09-26 06:55:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 643 ms / 5,000 ms
コード長 3,399 bytes
コンパイル時間 892 ms
コンパイル使用メモリ 59,176 KB
実行使用メモリ 124,480 KB
最終ジャッジ日時 2024-11-18 15:04:59
合計ジャッジ時間 11,458 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘M read(int, int)’:
main.cpp:69:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |                         scanf("%d", &x[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:159:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  159 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:165:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  165 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:169:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  169 |                 scanf(" %s%d", c, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> V;
typedef vector<V> M;
typedef pair<M, M> P;
struct T{
    M a, b, s;
};
const int mod = 1e9 + 7;
int add(int a, int b){
    return (a + b) % mod;
}
int mul(int a, int b){
    return ll(a) * b % mod;
}
M add(const M& a, const M& b){
    int n = a.size(), m = a[0].size();
    M c(n, V(m));
    rep(i, n){
        rep(j, m){
            c[i][j] = add(a[i][j], b[i][j]);
        }
    }
    return c;
}
M mul(const M& a, const M& b){
    int n = a.size(), m = b.size(), l = b[0].size();
    M c(n, V(l));
    rep(i, n){
        rep(k, l){
            int s = 0;
            rep(j, m){
                s = add(mul(a[i][j], b[j][k]), s);
            }
            c[i][k] = s;
        }
    }
    return c;
}
M col(const V& v){
    int n = v.size();
    M x(n, V(1));
    rep(i, n){
        x[i][0] = v[i];
    }
    return x;
}
M identity(int n){
    M x(n, V(n, 0));
    rep(i, n){
        x[i][i] = 1;
    }
    return x;
}
M read(int n, int m){
    M x(n, V(m));
    rep(i, n){
        rep(j, m){
            scanf("%d", &x[i][j]);
        }
    }
    return x;
}
void print(const M& x){
    int n = x.size();
    rep(i, n){
        printf("%d%c", x[i][0], i != n - 1 ? ' ' : '\n');
    }
}
int n, q;
M f, g;
M a[1 << 18];
M b[1 << 18];
M s[1 << 18];
M init(int k, int l, int r){
    if(l + 1 == r){
        int p = 6 * l;
        return s[k] = {{p, p + 1, p + 2}, {p + 3, p + 4, p + 5}}; 
    }
    int m = (l + r) / 2;
    return s[k] = add(init(2 * k + 1, l, m), init(2 * k + 2, m, r));
}
void init(){
    fill_n(a, 1 << 18, identity(3));
    fill_n(b, 1 << 18, identity(2));
    init(0, 0, n + 1);
}
P update_a(int i, const M& x, int k, int l, int r){
    if(i < l || r <= i){
        return P(a[k], s[k]);
    }
    if(i <= l && r <= i + 1){
        return P(a[k] = x, s[k]);
    }
    int m = (l + r) / 2;
    P p = update_a(i, x, 2 * k + 1, l, m);
    P q = update_a(i, x, 2 * k + 2, m, r);
    return P(
        a[k] = mul(q.first, p.first),
        s[k] = add(p.second, mul(mul(b[2 * k + 1], q.second), p.first))
    );
}
void update_a(int i, const M& x){
    update_a(i, x, 0, 0, n + 1);
}
P update_b(int i, const M& x, int k, int l, int r){
    if(i < l || r <= i){
        return P(b[k], s[k]);
    }
    if(i <= l && r <= i + 1){
        return P(b[k] = x, s[k]);
    }
    int m = (l + r) / 2;
    P p = update_b(i, x, 2 * k + 1, l, m);
    P q = update_b(i, x, 2 * k + 2, m, r);
    return P(
        b[k] = mul(p.first, q.first),
        s[k] = add(p.second, mul(mul(p.first, q.second), a[2 * k + 1]))
    );
}
void update_b(int i, const M& x){
    update_b(i, x, 0, 0, n + 1);
}
T query_abs(int f, int g, int k, int l, int r){
    if(g <= l || r <= f){
        return {identity(3), identity(2), M(2, V(3, 0))};
    }
    if(f <= l && r <= g){
        return {a[k], b[k], s[k]};
    }
    int m = (l + r) / 2;
    T p = query_abs(f, g, 2 * k + 1, l, m);
    T q = query_abs(f, g, 2 * k + 2, m, r);
    return {
        mul(q.a, p.a),
        mul(p.b, q.b),
        add(p.s, mul(mul(p.b, q.s), p.a))   
    };
}
T query_abs(int f, int g){
    return query_abs(f, g, 0, 0, n + 1);
}
int main(){
    scanf("%d", &n);
    f = read(3, 1);
    g = read(2, 1);
    init();
    scanf("%d", &q);
    rep(i, q){
        char c[3];
        int k;
        scanf(" %s%d", c, &k);
        if(c[0] == 'g'){
            if(c[1] == 'a'){
                T t = query_abs(0, k);
                print(mul(t.a, f));
            }
            else{
                T t = query_abs(0, k + 1);
                T u = query_abs(k + 1, n + 1);
                print(add(mul(u.b, g), mul(mul(u.s, t.a), f)));
            }
        }
        else{
            if(c[0] == 'a'){
                M x = read(3, 3);
                update_a(k, x);
            }
            else{
                M x = read(2, 2);
                update_b(k, x);
            }
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0