QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#92016#5408. 计数鸡syzf2222100 ✓70ms6108kbC++1.9kb2023-03-30 08:59:542023-03-30 08:59:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 08:59:56]
  • 评测
  • 测评结果:100
  • 用时:70ms
  • 内存:6108kb
  • [2023-03-30 08:59:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
const int inf=1e9;
const int iv2=(mod+1)/2;
#define ll long long
#define pc(x) __builtin_popcount(x)
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int N=305;
int n,m,q[N],h[N],S[N][N],a[N][N],det=1,fac=1;
int dp[1<<20][2];
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
inline int chk(int x){return min(max(0,x),n);}
inline void solve1(){
	dp[0][0]=1;
	for(int i=0;i<(1<<n);i++){
		//printf("i=%d %d %d\n",i,dp[i][0],dp[i][1]);
		int pos=pc(i)+1;
		for(int j=0;j<n;j++)if(!(i>>j&1)){
			int o=(pc(i>>j)+S[pos+1][chk(j+1+h[pos])])&1;
		//	printf("j=%d o=%d\n",j,o);
			for(int o1=0;o1<2;o1++)
				add(dp[i|(1<<j)][o1^o],dp[i][o1]);
		}
	}printf("%d\n",dp[(1<<n)-1][0]);
	exit(0);
}
inline int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}return res;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)q[i]=read();
	for(int i=1;i<=n;i++)h[i]=read();
	for(int i=n;i>=1;i--)
		for(int j=1;j<=n;j++)S[i][j]=S[i+1][j]+(j>=q[i]);
//	if(n<=20)solve1();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(S[i+1][chk(j+h[i])]&1)a[i][j]=mod-1;else a[i][j]=1;
	for(int i=1;i<=n;i++){
		int pos=0;
		for(int j=i;j<=n;j++)
			if(a[j][i]){pos=j;break;}
		if(pos^i){
			det=mod-det;
			for(int j=1;j<=n;j++)swap(a[i][j],a[pos][j]);
		}int iv=ksm(a[i][i],mod-2);
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			int kk=1ll*a[j][i]*iv%mod;
			for(int k=1;k<=n;k++)
				a[j][k]=(a[j][k]-1ll*a[i][k]*kk%mod+mod)%mod;
		}
	}for(int i=1;i<=n;i++)
		det=1ll*det*a[i][i]%mod;
	for(int i=1;i<=n;i++)
		fac=1ll*fac*i%mod;
	printf("%d\n",1ll*(det+fac)*iv2%mod);
	return 0;
}

詳細信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 2ms
memory: 3828kb

input:

20
20 4 15 16 11 3 7 18 9 5 13 8 6 12 2 10 1 17 14 19
-7 -11 9 -3 -20 -13 -18 15 0 8 0 12 -16 -19 8 -9 -4 -2 6 -10

output:

699910446

result:

ok 1 number(s): "699910446"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5580kb

input:

20
11 6 3 18 17 19 4 8 10 15 12 16 1 13 7 14 5 20 9 2
13 9 -1 1 9 -11 -19 8 -5 -11 -4 3 17 1 8 1 0 -11 -16 -10

output:

694405422

result:

ok 1 number(s): "694405422"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

20
11 12 16 6 5 2 8 20 14 7 13 15 4 9 19 3 10 1 17 18
-12 11 14 -9 0 0 -4 -3 14 -4 -14 16 -1 12 -19 8 -1 1 8 10

output:

699648302

result:

ok 1 number(s): "699648302"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

20
12 19 16 8 7 5 15 18 10 1 2 14 6 11 9 20 4 17 13 3
-14 -13 11 -3 -8 6 -14 -4 9 -4 12 -7 -8 7 4 13 3 8 -17 11

output:

693618990

result:

ok 1 number(s): "693618990"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

20
19 9 2 18 10 17 7 11 16 12 3 13 8 15 14 6 5 4 1 20
13 9 16 10 4 1 -2 -11 3 11 -7 18 -15 -2 -19 9 -8 -8 4 -19

output:

700172590

result:

ok 1 number(s): "700172590"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5692kb

input:

20
17 8 11 15 12 14 4 6 7 9 18 13 19 10 16 2 1 5 3 20
5 -19 6 -9 18 1 -8 -1 2 -12 7 -6 10 -4 -2 0 -9 -15 17 20

output:

700434734

result:

ok 1 number(s): "700434734"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3824kb

input:

20
2 17 20 5 11 18 1 14 12 8 9 6 7 16 13 15 10 4 19 3
-2 -9 -14 -13 -12 1 -7 2 8 3 -1 -5 -4 3 -9 6 -15 11 -14 -5

output:

694143278

result:

ok 1 number(s): "694143278"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

20
7 12 3 15 8 2 9 11 19 4 16 10 13 14 17 6 20 1 18 5
3 10 -6 3 3 -13 -9 -5 5 -11 -16 -17 -13 5 14 4 3 1 2 9

output:

697813294

result:

ok 1 number(s): "697813294"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

20
5 1 7 15 9 16 12 4 17 19 13 6 11 8 20 18 10 3 14 2
-16 13 -5 -10 8 2 -5 5 -15 -18 9 0 6 18 0 10 9 -7 -16 -11

output:

700959022

result:

ok 1 number(s): "700959022"

Test #10:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

20
16 10 17 12 19 13 20 2 7 3 15 14 5 8 11 1 4 18 9 6
14 4 16 4 9 -12 -4 11 3 14 -7 -10 -19 -4 0 -1 2 -9 4 6

output:

697551150

result:

ok 1 number(s): "697551150"

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 1ms
memory: 3612kb

input:

15
14 4 15 10 11 3 7 1 9 5 13 8 6 12 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985377138

result:

ok 1 number(s): "985377138"

Test #12:

score: 0
Accepted
time: 3ms
memory: 3776kb

input:

15
1 2 12 4 8 13 6 5 9 3 11 10 7 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985385330

result:

ok 1 number(s): "985385330"

Test #13:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

15
7 13 6 10 3 5 2 15 11 8 9 14 12 1 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985377138

result:

ok 1 number(s): "985377138"

Test #14:

score: 0
Accepted
time: 2ms
memory: 3888kb

input:

15
1 6 4 2 9 14 13 12 11 15 3 10 7 8 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985385330

result:

ok 1 number(s): "985385330"

Test #15:

score: 0
Accepted
time: 60ms
memory: 4484kb

input:

290
210 151 231 91 180 53 275 208 138 4 251 83 136 247 22 64 104 39 120 218 51 26 203 196 280 153 191 163 161 159 241 175 284 132 17 236 11 211 142 162 107 259 246 257 47 54 165 172 70 274 219 267 289 67 237 286 1 222 194 144 146 281 9 65 89 87 171 5 271 71 285 94 283 81 261 42 260 157 244 213 127 2...

output:

68391778

result:

ok 1 number(s): "68391778"

Test #16:

score: 0
Accepted
time: 60ms
memory: 4368kb

input:

293
1 170 64 256 155 245 196 19 106 108 262 104 235 56 232 6 143 140 226 65 177 202 174 133 193 263 96 191 176 114 113 91 161 290 165 30 128 83 152 53 240 139 12 154 156 118 203 252 90 68 49 208 153 59 21 198 66 280 163 182 105 149 35 79 220 239 236 151 3 276 269 93 127 189 225 237 110 228 212 109 3...

output:

31579777

result:

ok 1 number(s): "31579777"

Test #17:

score: 0
Accepted
time: 65ms
memory: 4500kb

input:

298
164 51 214 25 106 42 2 201 281 189 118 105 76 264 291 39 54 177 176 260 158 85 151 154 107 219 29 224 212 259 92 268 110 203 250 245 138 61 222 49 296 20 33 162 14 225 172 223 43 15 148 272 257 226 4 276 79 114 24 273 91 143 240 282 284 156 115 248 131 86 251 64 231 41 132 200 186 270 187 63 17 ...

output:

882980580

result:

ok 1 number(s): "882980580"

Test #18:

score: 0
Accepted
time: 68ms
memory: 4320kb

input:

291
1 95 126 139 63 31 267 240 237 145 276 179 151 220 69 256 278 208 261 112 289 55 200 155 247 18 284 27 129 169 262 22 61 185 29 175 174 229 249 94 73 2 226 75 147 290 199 110 10 215 124 198 52 93 211 121 137 171 128 64 51 204 186 109 135 254 122 48 26 246 96 236 144 157 23 30 239 263 47 282 148 ...

output:

991645574

result:

ok 1 number(s): "991645574"

Test #19:

score: 0
Accepted
time: 68ms
memory: 6032kb

input:

292
176 103 58 8 252 64 40 157 253 49 22 60 71 234 213 248 122 233 70 226 283 96 92 65 184 73 264 125 140 271 104 175 163 12 159 228 193 151 42 145 269 28 124 158 155 14 261 143 90 185 164 88 285 166 27 255 139 188 4 57 132 37 56 131 23 87 165 216 5 99 211 218 121 138 129 171 34 183 254 225 174 274 ...

output:

605781403

result:

ok 1 number(s): "605781403"

Test #20:

score: 0
Accepted
time: 55ms
memory: 4252kb

input:

290
1 99 242 93 198 161 155 49 56 2 48 43 248 207 239 240 157 138 126 289 81 275 258 70 261 177 171 251 241 112 101 145 109 121 136 15 286 141 260 285 72 271 103 139 63 64 229 129 209 196 42 222 76 53 277 172 162 212 92 265 263 221 4 282 246 182 45 119 132 134 152 175 34 223 226 236 114 183 46 27 59...

output:

595654396

result:

ok 1 number(s): "595654396"

Subtask #3:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #21:

score: 50
Accepted
time: 64ms
memory: 4364kb

input:

300
229 24 266 93 21 263 278 66 166 89 246 252 60 59 32 16 108 211 139 70 280 290 125 73 71 292 217 162 77 215 154 233 242 183 257 178 269 150 19 256 80 282 288 193 265 26 37 129 167 240 170 207 40 209 273 197 199 145 245 130 249 208 276 36 173 220 222 46 299 131 200 219 114 51 20 5 168 239 6 272 10...

output:

732190671

result:

ok 1 number(s): "732190671"

Test #22:

score: 0
Accepted
time: 65ms
memory: 4452kb

input:

300
95 119 128 87 250 238 195 160 12 212 295 222 221 233 66 192 197 79 35 24 18 49 198 98 64 82 72 75 266 32 181 114 227 259 107 90 109 134 154 200 253 225 69 3 120 155 26 30 265 270 234 273 130 196 287 133 293 137 48 122 205 21 282 60 83 61 166 183 202 148 5 38 207 117 52 73 51 263 186 180 146 272 ...

output:

755516354

result:

ok 1 number(s): "755516354"

Test #23:

score: 0
Accepted
time: 66ms
memory: 4288kb

input:

300
6 298 188 82 243 126 116 182 91 14 117 29 212 112 99 18 38 268 183 27 85 103 63 104 3 293 11 193 32 261 259 295 234 192 28 180 145 134 47 147 125 132 105 90 40 231 34 150 12 291 20 50 184 17 168 160 194 177 119 87 107 198 71 270 23 276 236 211 229 9 203 206 176 154 16 284 122 205 61 66 137 138 1...

output:

431309948

result:

ok 1 number(s): "431309948"

Test #24:

score: 0
Accepted
time: 70ms
memory: 4492kb

input:

300
60 267 114 9 84 71 295 111 279 37 171 247 78 1 164 205 160 130 10 202 262 27 208 253 8 200 100 280 147 35 70 286 75 138 215 185 131 218 292 53 272 80 282 96 170 223 21 48 137 40 203 244 123 230 165 14 242 62 110 299 55 288 151 93 278 51 198 210 56 231 85 54 261 217 68 297 197 166 121 252 12 188 ...

output:

4445444

result:

ok 1 number(s): "4445444"

Test #25:

score: 0
Accepted
time: 65ms
memory: 4496kb

input:

300
125 143 204 164 52 6 112 294 14 155 153 231 78 170 193 188 107 189 232 89 156 38 241 291 139 66 82 1 285 157 226 103 80 266 264 277 284 246 69 201 258 116 96 187 55 251 23 140 40 184 296 13 272 85 168 282 149 298 221 35 235 128 257 31 152 3 49 94 225 216 84 134 43 86 19 183 197 167 90 238 36 46 ...

output:

737349748

result:

ok 1 number(s): "737349748"

Test #26:

score: 0
Accepted
time: 67ms
memory: 4364kb

input:

300
244 187 129 110 45 257 165 242 138 145 209 78 71 140 224 35 219 84 196 245 118 211 183 228 207 105 83 226 256 27 102 249 241 172 114 64 297 188 186 179 199 115 180 234 288 65 51 277 231 142 210 50 296 52 181 49 291 99 268 206 252 260 127 119 97 101 4 299 6 247 193 147 103 56 36 8 250 22 253 267 ...

output:

992242884

result:

ok 1 number(s): "992242884"

Test #27:

score: 0
Accepted
time: 61ms
memory: 4332kb

input:

300
18 43 108 282 158 118 270 70 197 32 233 219 262 99 54 17 143 231 8 46 271 254 251 165 227 74 162 274 53 26 269 105 264 279 102 244 253 55 94 283 138 126 223 60 236 95 44 47 185 235 179 217 203 267 9 63 164 277 151 288 296 186 247 1 112 218 198 75 72 58 25 195 123 152 147 215 67 39 110 34 289 111...

output:

811650126

result:

ok 1 number(s): "811650126"

Test #28:

score: 0
Accepted
time: 66ms
memory: 4324kb

input:

300
96 211 299 16 176 253 62 296 247 207 265 224 113 143 278 287 39 88 137 269 206 85 163 17 18 131 36 162 56 147 60 208 3 69 59 150 168 197 105 97 34 12 221 244 248 47 170 53 98 83 234 181 133 164 50 6 148 13 282 117 195 193 172 102 229 157 139 32 286 61 280 260 103 281 159 33 45 187 99 200 31 90 4...

output:

654570274

result:

ok 1 number(s): "654570274"

Test #29:

score: 0
Accepted
time: 61ms
memory: 5812kb

input:

300
28 224 298 25 173 87 31 100 208 36 150 41 209 213 188 9 30 22 34 234 152 214 141 197 253 290 279 93 264 52 158 230 46 24 170 270 164 231 45 105 75 88 179 232 79 101 225 115 48 171 64 274 161 159 233 266 294 99 90 135 23 247 183 26 204 178 277 181 12 167 51 11 104 60 120 47 194 245 219 111 236 73...

output:

593839609

result:

ok 1 number(s): "593839609"

Test #30:

score: 0
Accepted
time: 66ms
memory: 6108kb

input:

300
281 216 85 247 241 283 217 184 282 65 203 43 1 255 218 252 121 47 284 186 291 130 205 235 44 29 263 276 293 239 59 215 81 261 199 274 246 264 27 296 101 80 156 207 155 224 154 106 21 297 166 182 141 158 167 118 187 62 153 135 147 289 93 64 75 128 268 60 292 245 286 161 159 25 74 136 195 221 173 ...

output:

586672614

result:

ok 1 number(s): "586672614"