結果

問題 No.426 往復漸化式
ユーザー rickythetarickytheta
提出日時 2016-09-23 02:15:37
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,233 bytes
コンパイル時間 1,953 ms
コンパイル使用メモリ 184,680 KB
実行使用メモリ 190,056 KB
最終ジャッジ日時 2024-04-28 20:28:47
合計ジャッジ時間 24,221 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,112 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 TLE -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:99:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   99 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
main.cpp:102:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |     scanf("%d%d%d",&x,&y,&z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:110:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |     scanf("%d%d",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~
main.cpp:116:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |   scanf("%d",&q);
      |   ~~~~~^~~~~~~~~
main.cpp:119:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  119 |     scanf("%s",qbuf);
      |     ~~~~~^~~~~~~~~~~
main.cpp:120:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  120 |     scanf("%d",&x);
      |     ~~~~~^~~~~~~~~
main.cpp:124:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  124 |       REP(j,3)REP(i,3)scanf("%lld",&po[i][j]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:129:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  129 |       REP(j,2)REP(i,2)scanf("%lld",&po[i][j]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

typedef vector<vi> mat;

mat mulmat(mat a,mat b){
  assert(a.size()>0 && b.size()>0 && a.size()==b[0].size());
  int n=a.size(), m=a[0].size(), l=b.size();
  mat ret(l,vi(m,0));
  REP(i,l)REP(j,m)REP(k,n)ret[i][j]=(ret[i][j]+a[k][j]*b[i][k])%MOD;
  return ret;
}
mat mulmat(mat a,ll k){
  mat ret(a.size(),vi(a[0].size()));
  REP(i,a.size())REP(j,a[0].size())ret[i][j]=a[i][j]*k%MOD;
  return ret;
}
mat addmat(mat a,mat b){
  assert(a.size()>0 && a.size()==b.size() && a[0].size()==b[0].size());
  mat ret(a.size(),vi(a[0].size()));
  REP(i,a.size())REP(j,a[0].size())ret[i][j]=(a[i][j]+b[i][j])%MOD;
  return ret;
}

int n;
mat a0,bn;
char qbuf[52];
map<int,mat> amat,bmat;
map<int,mat> avecmap;

mat sigma(int beg,int end){
  // calc sigma a_beg to a_end
  mat ret = mat(1,vi(2,0));
  if(beg>end)return ret;
  int cur = beg;
  map<int,mat>::iterator iter1;//,iter2;
  iter1 = avecmap.upper_bound(beg); iter1--;
  mat ai = iter1->second;
  int last = beg;
  iter1++;
  while(iter1!=avecmap.end()){
    int y = iter1->first;
    if(y>end)break;
    mat ci = mat(3,vi(2,6*beg));
    REP(i,3)REP(j,2)ci[i][j]+=3*j+i;
    ci = mulmat(ci,ai);
    int k = y-last;
    ret = addmat(ret,mulmat(ci,k));
    ll s = (ai[0][0]+ai[0][1]+ai[0][2])%MOD;
    ll po = k*(k-1)/2%MOD*s*6%MOD;
    ret[0][0]=(ret[0][0]+po)%MOD;
    ret[0][1]=(ret[0][1]+po)%MOD;
    last = y;
    ai = iter1->second;
    iter1++;
  }
  if(last<=end){
    mat ci = mat(3,vi(2,6*last));
    REP(i,3)REP(j,2)ci[i][j]+=3*j+i;
    ci = mulmat(ci,ai);
    int k = end-last+1;
    ret = addmat(ret,mulmat(ci,k));
    ll s = (ai[0][0]+ai[0][1]+ai[0][2])%MOD;
    ll po = k*(k-1)/2%MOD*s*6%MOD;
    ret[0][0]=(ret[0][0]+po)%MOD;
    ret[0][1]=(ret[0][1]+po)%MOD;
  }
  return ret;
}

int main(){
  scanf("%d",&n);
  {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    a0 = mat(1,vi(3));
    a0[0][0]=x;
    a0[0][1]=y;
    a0[0][2]=z;
  }
  {
    int x,y;
    scanf("%d%d",&x,&y);
    bn = mat(1,vi(2));
    bn[0][0]=x;
    bn[0][1]=y;
  }
  int q;
  scanf("%d",&q);
  while(q--){
    int x;
    scanf("%s",qbuf);
    scanf("%d",&x);
    if(qbuf[0]=='a'){
      // change A query
      mat po(3,vi(3));
      REP(j,3)REP(i,3)scanf("%lld",&po[i][j]);
      amat[x] = po;
    }else if(qbuf[0]=='b'){
      // change B query
      mat po(2,vi(2));
      REP(j,2)REP(i,2)scanf("%lld",&po[i][j]);
      bmat[x] = po;
    }else if(qbuf[1]=='a'){
      // calc A query
      mat ans = a0;
      map<int,mat>::iterator iter = amat.begin();
      while(iter!=amat.end()){
        int y = iter->first;
        if(y>=x)break;
        ans = mulmat(iter->second,ans);
        iter++;
      }
      printf("%lld %lld %lld\n",ans[0][0],ans[0][1],ans[0][2]);fflush(stdout);
    }else if(qbuf[1]=='b'){
      // calc B query
      avecmap.clear();
      avecmap[0] = a0;
      mat cur = a0;
      map<int,mat>::iterator iter = amat.begin();
      while(iter!=amat.end()){
        int y = iter->first;
        cur = mulmat(iter->second,cur);
        avecmap[y+1] = cur;
        iter++;
      }
      map<int,mat>::reverse_iterator iter2 = bmat.rbegin();
      mat ans = bn;
      int last = n;
      while(iter2!=bmat.rend()){
        int y = iter2->first;
        if(y<=x)break;
        ans = addmat(ans,sigma(y+1,last));
        ans = mulmat(iter2->second,ans);
        last = y;
        iter2++;
      }
      ans = addmat(ans,sigma(x+1,last));
      printf("%lld %lld\n",ans[0][0],ans[0][1]);fflush(stdout);
    }
  }
  return 0;
}
0