Submission #14860490

Source Code Expand

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define ROF(i,b,a) for (int i = (b)-1; i >= a; --i)
using namespace std;

const int N = 5010, P = 1e9+7;
typedef long long ll;

int qpow(int a, int x) {
	int ret = 1;
	for (; x; a = 1ll*a*a%P, x >>= 1) if (x&1) ret = 1ll*ret*a%P;
	return ret;
}

int n, m;
int f[N][N], s[N][N], pow2[N], inv2[N];

signed main() {
	scanf("%d%d", &m, &n);
	FOR(i,0,n+1) {
		pow2[i] = qpow(2, i);
		inv2[i] = qpow(2, P-1-i);
	}
	FOR(i,1,n+1) {
		f[0][i] = 1;
		s[0][i] = (s[0][i-1] + 1ll*inv2[i]*i%P*f[0][i])%P;
		//printf("s[%d][%d] = %d\n", 0, i, s[0][i]);
	}
	FOR(i,1,m+1) {
		FOR(j,1,n+1) {
			f[i][j] = ((j+1ll)*f[i-1][j] + 1ll*pow2[j-1]*s[i-1][j-1])%P;
			s[i][j] = (s[i][j-1] + 1ll*inv2[j]*j%P*f[i][j])%P;
			//printf("s[%d][%d] = %d\n", i, j, s[i][j]);
		}
	}
	printf("%d\n", f[m][n]);
}

Submission Info

Submission Time
Task F - Sorting Game
User frank3215
Language C++ (GCC 9.2.1)
Score 1000
Code Size 989 Byte
Status AC
Exec Time 234 ms
Memory 199556 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:24:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d%d", &m, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~

Judge Result

Set Name All Sample
Score / Max Score 1000 / 1000 0 / 0
Status
AC × 57
AC × 2
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_53.txt, testcase_54.txt, testcase_55.txt, testcase_6.txt, testcase_7.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 7 ms 3632 KiB
sample_02.txt AC 31 ms 28184 KiB
testcase_1.txt AC 2 ms 3748 KiB
testcase_10.txt AC 4 ms 3800 KiB
testcase_11.txt AC 1 ms 3800 KiB
testcase_12.txt AC 1 ms 3756 KiB
testcase_13.txt AC 3 ms 3744 KiB
testcase_14.txt AC 4 ms 3924 KiB
testcase_15.txt AC 5 ms 3968 KiB
testcase_16.txt AC 36 ms 43808 KiB
testcase_17.txt AC 38 ms 43768 KiB
testcase_18.txt AC 147 ms 141296 KiB
testcase_19.txt AC 232 ms 199512 KiB
testcase_2.txt AC 5 ms 3792 KiB
testcase_20.txt AC 231 ms 199476 KiB
testcase_21.txt AC 37 ms 43816 KiB
testcase_22.txt AC 37 ms 43820 KiB
testcase_23.txt AC 151 ms 141320 KiB
testcase_24.txt AC 232 ms 199556 KiB
testcase_25.txt AC 234 ms 199508 KiB
testcase_26.txt AC 22 ms 14392 KiB
testcase_27.txt AC 20 ms 21236 KiB
testcase_28.txt AC 52 ms 49236 KiB
testcase_29.txt AC 127 ms 113540 KiB
testcase_3.txt AC 5 ms 3856 KiB
testcase_30.txt AC 124 ms 118252 KiB
testcase_31.txt AC 115 ms 104960 KiB
testcase_32.txt AC 186 ms 159672 KiB
testcase_33.txt AC 73 ms 66492 KiB
testcase_34.txt AC 98 ms 79468 KiB
testcase_35.txt AC 28 ms 20036 KiB
testcase_36.txt AC 95 ms 87404 KiB
testcase_37.txt AC 75 ms 60664 KiB
testcase_38.txt AC 91 ms 90648 KiB
testcase_39.txt AC 150 ms 134628 KiB
testcase_4.txt AC 5 ms 3840 KiB
testcase_40.txt AC 26 ms 27664 KiB
testcase_41.txt AC 100 ms 87248 KiB
testcase_42.txt AC 128 ms 121036 KiB
testcase_43.txt AC 78 ms 66656 KiB
testcase_44.txt AC 113 ms 103964 KiB
testcase_45.txt AC 43 ms 31928 KiB
testcase_46.txt AC 75 ms 61872 KiB
testcase_47.txt AC 73 ms 72016 KiB
testcase_48.txt AC 165 ms 147556 KiB
testcase_49.txt AC 63 ms 47896 KiB
testcase_5.txt AC 7 ms 3764 KiB
testcase_50.txt AC 32 ms 24652 KiB
testcase_51.txt AC 170 ms 141224 KiB
testcase_52.txt AC 35 ms 21232 KiB
testcase_53.txt AC 195 ms 181324 KiB
testcase_54.txt AC 134 ms 126844 KiB
testcase_55.txt AC 217 ms 198140 KiB
testcase_6.txt AC 6 ms 3756 KiB
testcase_7.txt AC 3 ms 3756 KiB
testcase_8.txt AC 2 ms 3752 KiB
testcase_9.txt AC 7 ms 3892 KiB