QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#313388#7998. 矩阵ushg8877100 ✓7326ms885724kbC++142.2kb2024-01-24 18:30:122024-01-24 18:30:12

Judging History

你现在查看的是最新测评结果

  • [2024-01-24 18:30:12]
  • 评测
  • 测评结果:100
  • 用时:7326ms
  • 内存:885724kb
  • [2024-01-24 18:30:12]
  • 提交

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"