結果
| 問題 |
No.426 往復漸化式
|
| コンテスト | |
| ユーザー |
 rickytheta
|
| 提出日時 | 2016-09-23 02:15:37 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,233 bytes |
| コンパイル時間 | 2,212 ms |
| コンパイル使用メモリ | 184,428 KB |
| 実行使用メモリ | 10,496 KB |
| 最終ジャッジ日時 | 2024-11-17 15:55:18 |
| 合計ジャッジ時間 | 24,524 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 19 TLE * 3 |
コンパイルメッセージ
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]);
| ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#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;
}