QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#313388 | #7998. 矩阵 | ushg8877 | 100 ✓ | 7326ms | 885724kb | C++14 | 2.2kb | 2024-01-24 18:30:12 | 2024-01-24 18:30:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3005,mod=1e9+7;
const int dx[]={0,-1,0,1},dy[]={1,0,-1,0};
int n,q,a[N][N];
struct edge{edge *tw; ll w; int u;} e[N*N][4];
void link(edge &x,edge &y,ll w){
x.tw=&y,y.tw=&x,x.w=w,y.w=-w;
}
int getid(edge x){
int u=x.u,d=0;
while(e[u][d].tw!=x.tw) d=(d+1)&3;
return d;
}
edge& turn(edge x,int an){
int i=getid(x); i=(i+an)&3;
return e[x.u][i];
}
edge gps(int x,int y,ll &sum){
edge a=e[0][0];
for(int i=1;i<=y;++i) sum+=a.w,a=turn(*a.tw,2);
a=turn(a,3);
for(int i=1;i<=x;++i) sum+=a.w,a=turn(*a.tw,2);
return a;
}
vector<pair<edge*,ll>> inner,outer;
void tour(edge &p,int d,ll &sum){
for(int i=1;i<=d;++i){
sum+=p.w,p=turn(*p.tw,2);
auto &q=turn(p,3);
outer.emplace_back(&q,sum);
inner.emplace_back(q.tw,sum+q.w);
}
sum+=p.w,p=turn(*p.tw,1);
}
void rotate(int u,int l,int d,int r){
int m=d-u+1; ll val=0;
auto p=gps(u-1,l-1,val); p=turn(p,1);
for(int o=0;o<4;++o) tour(p,m,val);
for(int i=0;i<4*m;++i){
auto p=outer[i],q=inner[(i+m)%(4*m)];
link(*p.first,*q.first,q.second-p.second);
}
}
void add(int u,int l,int d,int r,ll w){
ll val=0;
auto p=gps(u-1,l-1,val); p=turn(p,1);
tour(p,r-l+1,val),tour(p,d-u+1,val),tour(p,r-l+1,val),tour(p,d-u+1,val);
for(int i=0;i<outer.size();++i){
auto p=outer[i],q=inner[i];
p.first->w+=w,q.first->w-=w;
}
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;++i)
for(int j=1,w=i+1;j<=n;++j,w=1ll*w*(i+1)%998244353) a[i][j]=w;
for(int i=0;i<=n+1;++i)
for(int j=0;j<=n+1;++j)
for(int d=0;d<4;++d){
int nx=i+dx[d],ny=j+dy[d];
if(nx>=0&&nx<=n+1&&ny>=0&&ny<=n+1)
e[i*(n+2)+j][d]={&e[nx*(n+2)+ny][d^2],a[nx][ny]-a[i][j],i*(n+2)+j};
}
for(int o,u,d,l,r,v;q--;){
scanf("%d%d%d%d%d",&o,&u,&l,&d,&r);
outer.clear(),inner.clear();
if(o==1) rotate(u,l,d,r);
else scanf("%d",&v),add(u,l,d,r,v);
}
edge p=e[0][3]; ll sum=0; int ans=0;
for(int i=1,b=12345;i<=n;++i){
sum+=p.w,p=turn(*p.tw,2);
auto q=turn(p,1); ll val=sum;
for(int j=1;j<=n;++j,b=12345ll*b%mod){
val+=q.w,q=turn(*q.tw,2);
ans=(ans+1ll*b*(val%mod+mod))%mod;
}
}
cout<<ans;
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 16ms
memory: 8564kb
input:
100 3000 1 4 3 100 99 1 3 8 83 88 1 4 7 96 99 1 2 7 90 95 2 6 5 98 98 762240996 1 9 8 98 97 1 3 3 100 100 2 18 7 97 84 230446266 1 2 5 94 97 1 2 18 82 98 1 9 2 100 93 1 3 9 91 97 1 1 2 99 100 1 7 6 98 97 1 2 4 98 100 1 3 2 99 98 1 4 2 100 98 2 9 74 28 83 703323901 1 6 4 100 98 2 2 6 99 93 882702932 ...
output:
535773693
result:
ok 1 number(s): "535773693"
Test #2:
score: 10
Accepted
time: 3597ms
memory: 885376kb
input:
3000 3000 2 40 215 2496 2298 67590963 2 100 211 2684 2855 670656770 2 417 399 2612 2930 826127245 2 116 779 2407 2596 977282152 2 512 366 2768 2949 737671139 2 191 594 2671 2978 404448620 2 3 11 2720 2633 516813112 2 95 294 2553 2820 112269230 2 284 58 2934 2754 225336228 2 306 53 2815 2984 49218367...
output:
343427775
result:
ok 1 number(s): "343427775"
Test #3:
score: 10
Accepted
time: 5040ms
memory: 885724kb
input:
3000 2000 1 853 610 2674 2431 1 24 415 2490 2881 1 19 150 2842 2973 1 597 79 2977 2459 1 307 408 2397 2498 1 292 316 2907 2931 1 7 42 2953 2988 1 36 30 2953 2947 1 55 438 2609 2992 1 97 204 2664 2771 1 607 254 2803 2450 1 59 159 2808 2908 1 58 12 2991 2945 1 287 400 2506 2619 1 105 143 2949 2987 1 2...
output:
743809971
result:
ok 1 number(s): "743809971"
Test #4:
score: 10
Accepted
time: 4995ms
memory: 885532kb
input:
3000 2000 1 646 55 2815 2224 1 47 78 2964 2995 1 48 7 2882 2841 1 9 8 2999 2998 1 128 36 2984 2892 1 14 5 2990 2981 1 52 81 2934 2963 1 231 317 2612 2698 1 33 7 2960 2934 1 111 165 2732 2786 1 9 2 2994 2987 1 131 224 2866 2959 1 19 49 2917 2947 1 46 44 2997 2995 1 1 14 2969 2982 1 69 49 2975 2955 1 ...
output:
517390609
result:
ok 1 number(s): "517390609"
Test #5:
score: 10
Accepted
time: 7300ms
memory: 884876kb
input:
3000 3000 1 6 5 2997 2996 1 14 362 2624 2972 1 657 108 2405 1856 1 20 27 2983 2990 1 245 236 2903 2894 1 184 100 2957 2873 1 61 47 2954 2940 1 39 89 2935 2985 1 43 49 2956 2962 1 132 138 2763 2769 1 4 4 2998 2998 1 16 59 2752 2795 1 30 24 2997 2991 1 143 11 2959 2827 1 57 44 2887 2874 1 40 17 2991 2...
output:
632994577
result:
ok 1 number(s): "632994577"
Test #6:
score: 10
Accepted
time: 7326ms
memory: 885212kb
input:
3000 3000 1 544 5 2907 2368 1 60 63 2978 2981 1 228 310 2881 2963 1 57 71 2958 2972 1 101 565 2467 2931 1 979 1004 2882 2907 1 37 3 2913 2879 1 418 427 2922 2931 1 30 62 2937 2969 1 83 104 2979 3000 1 4 18 2939 2953 1 67 203 2834 2970 1 357 882 1000 1525 1 34 10 2991 2967 1 8 4 2997 2993 1 2 4 2991 ...
output:
275056325
result:
ok 1 number(s): "275056325"
Test #7:
score: 10
Accepted
time: 4418ms
memory: 884288kb
input:
3000 2000 1 82 42 2883 2843 1 2 48 2939 2985 2 188 176 2376 2976 715286463 1 15 24 2984 2993 1 106 50 2811 2755 2 45 132 2745 2432 339749026 1 5 100 2779 2874 1 343 134 2478 2269 1 106 227 2820 2941 2 10 206 2947 2798 365598855 2 560 106 2582 2903 92795190 1 74 100 2960 2986 1 5 33 2944 2972 2 873 3...
output:
191562107
result:
ok 1 number(s): "191562107"
Test #8:
score: 10
Accepted
time: 4348ms
memory: 885588kb
input:
3000 2000 1 20 5 2990 2975 1 14 10 2999 2995 1 192 89 2950 2847 2 547 646 2654 2940 439095457 1 18 16 3000 2998 1 35 105 2754 2824 1 17 52 2942 2977 2 356 121 2384 2963 959830720 2 76 78 2412 1842 361763869 2 199 46 2624 2931 743439747 2 180 320 2981 2964 772483137 2 173 122 2732 2901 759079379 1 47...
output:
787136396
result:
ok 1 number(s): "787136396"
Test #9:
score: 10
Accepted
time: 6322ms
memory: 885592kb
input:
3000 3000 1 220 131 2785 2696 2 1443 1396 2159 2850 578335729 1 536 1184 1545 2193 1 26 23 2999 2996 1 43 56 2881 2894 1 29 4 2872 2847 2 69 155 2681 2931 88398671 1 66 44 2945 2923 1 53 512 2515 2974 2 402 58 2752 2782 641047796 2 458 36 2859 2756 694998888 2 145 192 2995 2973 483103477 1 117 315 2...
output:
973923858
result:
ok 1 number(s): "973923858"
Test #10:
score: 10
Accepted
time: 6306ms
memory: 884940kb
input:
3000 3000 2 7 47 2887 2544 535526356 2 160 639 2988 2995 343766215 1 122 40 2985 2903 2 62 240 2858 2177 841981272 1 169 18 2682 2531 1 61 286 2729 2954 1 180 27 2994 2841 1 238 330 2881 2973 2 57 188 2880 2914 203515190 1 28 61 2903 2936 2 102 269 2876 2397 681849386 1 3 53 2896 2946 1 101 56 2985 ...
output:
328382756
result:
ok 1 number(s): "328382756"