結果
| 問題 |
No.650 行列木クエリ
|
| ユーザー |
 ryoissy
|
| 提出日時 | 2018-02-10 00:07:45 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 499 ms / 2,000 ms |
| コード長 | 4,151 bytes |
| コンパイル時間 | 2,448 ms |
| コンパイル使用メモリ | 185,168 KB |
| 実行使用メモリ | 117,164 KB |
| 最終ジャッジ日時 | 2024-10-09 09:04:54 |
| 合計ジャッジ時間 | 5,089 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:192:35: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*’ {aka ‘long long int*’} [-Wformat=]
192 | scanf("%d%d%d%d%d%*c",&v,&C[0][0],&C[0][1],&C[1][0],&C[1][1]);
| ~^
| |
| int*
| %lld
main.cpp:192:37: warning: format ‘%d’ expects argument of type ‘int*’, but argument 4 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*’ {aka ‘long long int*’} [-Wformat=]
192 | scanf("%d%d%d%d%d%*c",&v,&C[0][0],&C[0][1],&C[1][0],&C[1][1]);
| ~^
| |
| int*
| %lld
main.cpp:192:39: warning: format ‘%d’ expects argument of type ‘int*’, but argument 5 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*’ {aka ‘long long int*’} [-Wformat=]
192 | scanf("%d%d%d%d%d%*c",&v,&C[0][0],&C[0][1],&C[1][0],&C[1][1]);
| ~^
| |
| int*
| %lld
main.cpp:192:41: warning: format ‘%d’ expects argument of type ‘int*’, but argument 6 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*’ {aka ‘long long int*’} [-Wformat=]
192 | scanf("%d%d%d%d%d%*c",&v,&C[0][0],&C[0][1],&C[1][0],&C[1][1]);
| ~^
|
ソースコード
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll extgcd(ll a,ll b,ll& x,ll& y){
ll d=a;
if(b!=0LL){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}else{
x=1;
y=0;
}
return d;
}
ll mod_inverse(ll a,ll m){
ll x,y;
extgcd(a,m,x,y);
return (m+x%m)%m;
}
typedef vector<ll> vec;
typedef vector<vec> mat;
mat mul(mat A,mat B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++){
for(int k=0;k<B.size();k++){
for(int j=0;j<B[0].size();j++){
C[i][j]=(C[i][j]+(A[i][k]*B[k][j]%MOD))%MOD;
}
}
}
return C;
}
int N[100001];
class segtree{
public:
vector<mat> dp;
mat ta;
segtree(){
ta.push_back(vec());
ta.push_back(vec());
ta[0].resize(2);
ta[1].resize(2);
ta[0][0]=1;
ta[0][1]=0;
ta[1][0]=0;
ta[1][1]=1;
}
void init(int n,int qi){
dp.clear();
N[qi]=1;
while(N[qi]<n){
N[qi]*=2;
}
for(int i=0;i<N[qi]*2;i++){
dp.push_back(mat());
dp[i].push_back(vec());
dp[i].push_back(vec());
dp[i][0].resize(2);
dp[i][1].resize(2);
dp[i][0][0]=1;
dp[i][0][1]=0;
dp[i][1][0]=0;
dp[i][1][1]=1;
}
}
void update(int k,int qi,mat v){
//printf("%d\n",k);
k+=N[qi]-1;
//printf("%d\n",k);
dp[k]=v;
while(k>0){
k=(k-1)/2;
dp[k]=mul(dp[k*2+1],dp[k*2+2]);
}
}
mat query(int a,int b,int k,int l,int r){
if(b<=l || r<=a)return ta;
if(a<=l && r<=b)return dp[k];
int mid=(l+r)/2;
mat vl=query(a,b,k*2+1,l,mid);
mat vr=query(a,b,k*2+2,mid,r);
return mul(vl,vr);
}
};
int n,q;
mat val[100001];
mat sum[100001];
vector<int> G[100001];
int depth[100001];
int siz[100001];
int hlsize=0;
vector<int> hls[100001];
int which[100001][2];
int parent[100001];
segtree seg[100001];
int kouh[100001][2];
int dfs(int v,int p,int c){
depth[v]=c;
sum[v]=mul(sum[v],val[v]);
int cnt=1;
for(int i=0;i<G[v].size();i++){
if(G[v][i]!=p){
cnt+=dfs(G[v][i],v,c+1);
}
}
return (siz[v]=cnt);
}
void constr(int v,int p,int id){
which[v][0]=id;
which[v][1]=hls[id].size();
hls[id].push_back(v);
int b=-1;
for(int i=0;i<G[v].size();i++){
if(G[v][i]!=p){
if(b==-1){
b=G[v][i];
}else if(siz[G[v][i]]>siz[b]){
b=G[v][i];
}
}
}
for(int i=0;i<G[v].size();i++){
if(G[v][i]!=p){
if(b==G[v][i]){
constr(G[v][i],v,id);
}else{
parent[hlsize]=v;
constr(G[v][i],v,hlsize++);
}
}
}
}
int main(void){
//printf("done\n");
scanf("%d",&n);
for(int i=0;i<n;i++){
val[i].push_back(vec());
val[i].push_back(vec());
val[i][0].resize(2);
val[i][1].resize(2);
val[i][0][0]=1;
val[i][0][1]=0;
val[i][1][0]=0;
val[i][1][1]=1;
sum[i].push_back(vec());
sum[i].push_back(vec());
sum[i][0].resize(2);
sum[i][1].resize(2);
sum[i][0][0]=1;
sum[i][0][1]=0;
sum[i][1][0]=0;
sum[i][1][1]=1;
}
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d%*c",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
kouh[i][0]=a;
kouh[i][1]=b;
}
scanf("%d%*c",&q);
dfs(0,-1,0);
hlsize++;
constr(0,-1,0);
//printf("done\n");
for(int i=0;i<hlsize;i++){
//printf("%d\n",(int)hls[i].size());
seg[i].init((int)hls[i].size(),i);
}
for(int i=0;i<q;i++){
char t;
scanf("%c",&t);
if(t=='x'){
mat C(2,vec(2));
int v;
scanf("%d%d%d%d%d%*c",&v,&C[0][0],&C[0][1],&C[1][0],&C[1][1]);
if(depth[kouh[v][0]]>depth[kouh[v][1]])v=kouh[v][0];
else v=kouh[v][1];
//printf("%d %d %d\n",v,which[v][0],which[v][1]);
seg[which[v][0]].update(which[v][1],which[v][0],C);
}else{
int f,t;
scanf("%d%d%*c",&f,&t);
mat ans(2,vec(2));
ans[0][0]=1;
ans[0][1]=0;
ans[1][0]=0;
ans[1][1]=1;
while(which[f][0]!=which[t][0]){
ans=mul(seg[which[t][0]].query(0,which[t][1]+1,0,0,N[which[t][0]]),ans);
t=parent[which[t][0]];
//printf("%d ",t);
//printf("%lld %lld %lld %lld\n",ans[0][0],ans[0][1],ans[1][0],ans[1][1]);
}
//sprintf("end\n");
ans=mul(seg[which[f][0]].query(which[f][1]+1,which[t][1]+1,0,0,N[which[f][0]]),ans);
//printf("%d %d %d %d\n",which[f][0],which[f][1],which[t][0],which[t][1]);
printf("%lld %lld %lld %lld\n",ans[0][0],ans[0][1],ans[1][0],ans[1][1]);
}
}
return 0;
}