Here are the editorials for all the problems. Hope you enjoyed them and found them interesting!↵
↵
[tutorial:711A]↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int INF = 1e9 + 7;↵
const int MOD = 1e9 + 7;↵
const int N = 1000;↵
char bus[N][5];↵
↵
void printbus(int n)↵
{↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < 5; j++)↵
{↵
cout << bus[i][j];↵
}↵
cout << '\n';↵
}↵
}↵
↵
void yes()↵
{↵
cout << "YES" << '\n';↵
}↵
↵
void no()↵
{↵
cout << "NO" << '\n';↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n; cin >> n;↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < 5; j++)↵
{↵
cin >> bus[i][j];↵
}↵
}↵
bool possible = false;↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < 2; j++)↵
{↵
if(bus[i][j*3] == 'O' && bus[i][j*3+1] == 'O')↵
{↵
bus[i][j*3] = '+';↵
bus[i][j*3+1] = '+';↵
possible = true;↵
break;↵
}↵
}↵
if(possible) break;↵
}↵
if(!possible)↵
{↵
no();↵
return 0;↵
}↵
else↵
{↵
yes();↵
printbus(n);↵
return 0;↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:711B]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int INF = 1e9 + 7;↵
const int MOD = 1e9 + 7;↵
const int LG = 20;↵
↵
ll a[1001][1001];↵
ll r[1001]; //row sum↵
ll c[1001]; //column sum↵
int n;↵
↵
void no()↵
{↵
cout << -1 << '\n';↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
cin >> n;↵
int x, y; ll diagonal1 = 0; ll diagonal2 = 0;↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < n; j++)↵
{↵
cin >> a[i][j];↵
if(a[i][j] == 0)↵
{↵
x = i; y = j;↵
}↵
else↵
{↵
r[i] += a[i][j];↵
c[j] += a[i][j];↵
if(i == j)↵
{↵
diagonal1 += a[i][j];↵
}↵
if(i + j == n - 1)↵
{↵
diagonal2 += a[i][j];↵
}↵
}↵
}↵
}↵
if(n == 1)↵
{↵
cout << 1 << '\n';↵
return 0;↵
}↵
ll commonsum = r[0];↵
if(x == 0) commonsum = r[1];↵
//cout << commonsum << '\n';↵
ll rowsum = -1; ll colsum = -1; ll d1sum = -1; ll d2sum = -1;↵
for(int i = 0; i < n; i++)↵
{↵
if(i != x)↵
{↵
if(r[i] != commonsum)↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
rowsum = r[i];↵
}↵
}↵
for(int i = 0; i < n; i++)↵
{↵
if(i != y)↵
{↵
if(c[i] != commonsum)↵
{↵
no(); return 0;↵
}↵
}↵
else↵
{↵
colsum = c[i];↵
}↵
}↵
bool isdiagonal1 = false; bool isdiagonal2 = false;↵
if(x == y) isdiagonal1 = true;↵
if(x + y == n - 1) isdiagonal2 = true;↵
if(!isdiagonal1)↵
{↵
if(diagonal1 != commonsum)↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
d1sum = diagonal1;↵
}↵
if(!isdiagonal2)↵
{↵
if(diagonal2 != commonsum)↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
d2sum = diagonal2;↵
}↵
if(rowsum == colsum)↵
{↵
if(isdiagonal1 && d1sum != rowsum)↵
{↵
no();↵
return 0;↵
}↵
if(isdiagonal2 && d2sum != rowsum)↵
{↵
no();↵
return 0;↵
}↵
ll value = commonsum - rowsum;↵
if(value > 0)↵
{↵
cout << value << '\n';↵
return 0;↵
}↵
else↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
no();↵
return 0;↵
}↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:711C]↵
↵
<spoiler summary="Code (O(nkm^2))">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int N = 101;↵
const int MOD = 1e9 + 7;↵
const ll INF = ll(1e18);↵
↵
ll dp[N][N][N];↵
int c[N];↵
ll cost[N][N];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n, m, k; cin >> n >> m >> k;↵
for(int i = 1; i <= n; i++)↵
{↵
cin >> c[i];↵
}↵
for(int i = 0; i <= n; i++)↵
{↵
for(int j = 0; j <= k; j++)↵
{↵
for(int a = 0; a <= m; a++)↵
{↵
dp[i][j][a] = INF;↵
}↵
}↵
}↵
for(int i = 1; i <= n; i++)↵
{↵
for(int j = 1; j <= m; j++)↵
{↵
cin >> cost[i][j];↵
}↵
}↵
if(c[1] == 0)↵
{↵
for(int i = 1; i <= m; i++)↵
{↵
dp[1][1][i] = cost[1][i];↵
}↵
}↵
else↵
{↵
dp[1][1][c[1]] = 0;↵
}↵
for(int i = 2; i <= n; i++)↵
{↵
for(int j = 1; j <= k; j++)↵
{↵
if(c[i] == 0)↵
{↵
for(int a = 1; a <= m; a++)↵
{↵
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);↵
for(int b = 1; b <= m; b++)↵
{↵
if(b != a) dp[i][j][a] = min(dp[i][j][a], dp[i-1][j-1][b] + cost[i][a]);↵
}↵
}↵
}↵
else↵
{↵
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);↵
for(int b = 1; b <= m; b++)↵
{↵
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);↵
}↵
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';↵
}↵
}↵
}↵
ll ans = INF;↵
for(int i = 1; i <= m; i++)↵
{↵
ans = min(ans, dp[n][k][i]);↵
}↵
if(ans >= INF) ans = -1;↵
cout << ans;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code (O(nkm))">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int N = 101;↵
const int MOD = 1e9 + 7;↵
const ll INF = ll(1e18);↵
↵
ll dp[N][N][N];↵
int c[N];↵
ll cost[N][N];↵
ll idx[N][N];↵
ll m1[N][N];↵
ll m2[N][N];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n, m, k; cin >> n >> m >> k;↵
for(int i = 1; i <= n; i++)↵
{↵
cin >> c[i];↵
}↵
for(int i = 0; i <= n; i++)↵
{↵
for(int j = 0; j <= k; j++)↵
{↵
m1[i][j] = INF; m2[i][j] = INF; idx[i][j] = -1;↵
for(int a = 0; a <= m; a++)↵
{↵
dp[i][j][a] = INF;↵
}↵
}↵
}↵
for(int i = 1; i <= n; i++)↵
{↵
for(int j = 1; j <= m; j++)↵
{↵
cin >> cost[i][j];↵
}↵
}↵
if(c[1] == 0)↵
{↵
for(int i = 1; i <= m; i++)↵
{↵
dp[1][1][i] = cost[1][i];↵
if(dp[1][1][i] <= m1[1][1])↵
{↵
if(dp[1][1][i] == m1[1][1])↵
{↵
idx[1][1] = -2;↵
}↵
else↵
{↵
idx[1][1] = i;↵
}↵
m2[1][1] = m1[1][1];↵
m1[1][1] = dp[1][1][i];↵
}↵
else if(dp[1][1][i] <= m2[1][1])↵
{↵
m2[1][1] = dp[1][1][i];↵
}↵
}↵
}↵
else↵
{↵
dp[1][1][c[1]] = 0;↵
m1[1][1] = 0; idx[1][1] = c[1];↵
}↵
for(int i = 2; i <= n; i++)↵
{↵
for(int j = 1; j <= k; j++)↵
{↵
if(c[i] == 0)↵
{↵
for(int a = 1; a <= m; a++)↵
{↵
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);↵
ll tmp = INF;↵
if(a == idx[i-1][j-1])↵
{↵
tmp = m2[i-1][j-1];↵
}↵
else↵
{↵
tmp = m1[i-1][j-1];↵
}↵
dp[i][j][a] = min(dp[i][j][a], tmp + cost[i][a]);↵
}↵
}↵
else↵
{↵
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);↵
for(int b = 1; b <= m; b++)↵
{↵
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);↵
}↵
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';↵
}↵
for(int a = 1; a <= m; a++)↵
{↵
if(dp[i][j][a] <= m1[i][j])↵
{↵
if(dp[i][j][a] == m1[i][j])↵
{↵
idx[i][j] = -2;↵
}↵
else↵
{↵
idx[i][j] = a;↵
}↵
m2[i][j] = m1[i][j];↵
m1[i][j] = dp[i][j][a];↵
}↵
else if(dp[i][j][a] <= m2[i][j])↵
{↵
m2[i][j] = dp[i][j][a];↵
}↵
}↵
}↵
}↵
ll ans = INF;↵
for(int i = 1; i <= m; i++)↵
{↵
ans = min(ans, dp[n][k][i]);↵
}↵
if(ans >= INF) ans = -1;↵
cout << ans;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:711D]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int INF = 1e9 + 7;↵
const int MOD = 1e9 + 7;↵
const int N = 1e6 + 3;↵
↵
int a[N];↵
int visited[N];↵
ll ans;↵
vector<int> cycles;↵
ll dp[N];↵
int cyclecnt;↵
↵
void dfs2(int u)↵
{↵
cycles[cyclecnt]++;↵
visited[u] = 3;↵
if(visited[a[u]] == 3) return ;↵
dfs2(a[u]);↵
}↵
↵
void dfs(int u)↵
{↵
visited[u] = 2;↵
if(visited[a[u]] == 0)↵
{↵
dfs(a[u]);↵
}↵
else if(visited[a[u]] == 1)↵
{↵
visited[u] = 1;↵
return ;↵
}↵
else↵
{↵
cycles.pb(0);↵
dfs2(u);↵
cyclecnt++;↵
}↵
visited[u] = 1;↵
}↵
↵
int main()↵
{↵
//ios_base::sync_with_stdio(0); cin.tie(0);↵
int n; scanf("%d", &n);↵
for(int i = 1; i <= n; i++)↵
{↵
scanf("%d", a + i);↵
}↵
dp[0] = 1;↵
for(int i = 1; i <= n; i++)↵
{↵
dp[i] = (dp[i-1]*2LL)%MOD;↵
}↵
ans = 1;↵
memset(visited, 0, sizeof(visited));↵
for(int i = 1; i <= n; i++)↵
{↵
if(visited[i] == 0)↵
{↵
dfs(i);↵
}↵
}↵
ll cnt = n;↵
for(int i = 0; i < cycles.size(); i++)↵
{↵
cnt -= cycles[i];↵
ans = (ans*(dp[cycles[i]]-2+MOD))%MOD;↵
}↵
ans = (ans*dp[cnt])%MOD;↵
if(ans < 0) ans += MOD;↵
int ans2 = ans;↵
printf("%d\n", ans2);↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:711E]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef vector<int> vi;↵
↵
const int MOD = 1e6 + 3;↵
↵
ll power(ll base, ll exp)↵
{↵
ll ans = 1;↵
while(exp)↵
{↵
if(exp&1) ans = (ans*base)%MOD;↵
base = (base*base)%MOD;↵
exp>>=1;↵
}↵
return ans;↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
ll n, k;↵
cin >> n >> k;↵
if(n <= 63 && k > (1LL<<n))↵
{↵
cout << 1 << " " << 1;↵
return 0;↵
}↵
ll v2 = 0;↵
int digits = __builtin_popcountll(k - 1);↵
v2 = k - 1 - digits;↵
ll ntmp = n % (MOD - 1);↵
if(ntmp < 0) ntmp += (MOD - 1);↵
ll ktmp = k % (MOD - 1);↵
if(ktmp < 0) ktmp += (MOD - 1);↵
ll v2tmp = v2 % (MOD - 1);↵
if(v2tmp < 0) v2tmp += (MOD - 1);↵
ll exponent = ntmp*(ktmp - 1) - v2tmp;↵
exponent %= (MOD - 1);↵
if(exponent < 0) exponent += MOD - 1;↵
ll denom = power(2, exponent);↵
ll numpart = 0;↵
if(k - 1 >= MOD)↵
{↵
numpart = 0;↵
}↵
else↵
{↵
ll prod = 1;↵
ll ntmp2 = power(2, ntmp);↵
prod = power(2, v2tmp);↵
prod = power(prod, MOD - 2);↵
if(prod < 0) prod += MOD;↵
for(ll y = 1; y <= k - 1; y++)↵
{↵
prod = (prod * (ntmp2 - y))%MOD;↵
}↵
numpart = prod;↵
}↵
ll num = (denom - numpart)%MOD;↵
num %= MOD; denom %= MOD;↵
if(num < 0) num += MOD;↵
if(denom < 0) denom += MOD;↵
cout << num << " " << denom;↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
The tutorial currently shows that it is unavailable for now. It will appear after system tests.
↵
[tutorial:711A]↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int INF = 1e9 + 7;↵
const int MOD = 1e9 + 7;↵
const int N = 1000;↵
char bus[N][5];↵
↵
void printbus(int n)↵
{↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < 5; j++)↵
{↵
cout << bus[i][j];↵
}↵
cout << '\n';↵
}↵
}↵
↵
void yes()↵
{↵
cout << "YES" << '\n';↵
}↵
↵
void no()↵
{↵
cout << "NO" << '\n';↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n; cin >> n;↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < 5; j++)↵
{↵
cin >> bus[i][j];↵
}↵
}↵
bool possible = false;↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < 2; j++)↵
{↵
if(bus[i][j*3] == 'O' && bus[i][j*3+1] == 'O')↵
{↵
bus[i][j*3] = '+';↵
bus[i][j*3+1] = '+';↵
possible = true;↵
break;↵
}↵
}↵
if(possible) break;↵
}↵
if(!possible)↵
{↵
no();↵
return 0;↵
}↵
else↵
{↵
yes();↵
printbus(n);↵
return 0;↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:711B]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int INF = 1e9 + 7;↵
const int MOD = 1e9 + 7;↵
const int LG = 20;↵
↵
ll a[1001][1001];↵
ll r[1001]; //row sum↵
ll c[1001]; //column sum↵
int n;↵
↵
void no()↵
{↵
cout << -1 << '\n';↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
cin >> n;↵
int x, y; ll diagonal1 = 0; ll diagonal2 = 0;↵
for(int i = 0; i < n; i++)↵
{↵
for(int j = 0; j < n; j++)↵
{↵
cin >> a[i][j];↵
if(a[i][j] == 0)↵
{↵
x = i; y = j;↵
}↵
else↵
{↵
r[i] += a[i][j];↵
c[j] += a[i][j];↵
if(i == j)↵
{↵
diagonal1 += a[i][j];↵
}↵
if(i + j == n - 1)↵
{↵
diagonal2 += a[i][j];↵
}↵
}↵
}↵
}↵
if(n == 1)↵
{↵
cout << 1 << '\n';↵
return 0;↵
}↵
ll commonsum = r[0];↵
if(x == 0) commonsum = r[1];↵
//cout << commonsum << '\n';↵
ll rowsum = -1; ll colsum = -1; ll d1sum = -1; ll d2sum = -1;↵
for(int i = 0; i < n; i++)↵
{↵
if(i != x)↵
{↵
if(r[i] != commonsum)↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
rowsum = r[i];↵
}↵
}↵
for(int i = 0; i < n; i++)↵
{↵
if(i != y)↵
{↵
if(c[i] != commonsum)↵
{↵
no(); return 0;↵
}↵
}↵
else↵
{↵
colsum = c[i];↵
}↵
}↵
bool isdiagonal1 = false; bool isdiagonal2 = false;↵
if(x == y) isdiagonal1 = true;↵
if(x + y == n - 1) isdiagonal2 = true;↵
if(!isdiagonal1)↵
{↵
if(diagonal1 != commonsum)↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
d1sum = diagonal1;↵
}↵
if(!isdiagonal2)↵
{↵
if(diagonal2 != commonsum)↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
d2sum = diagonal2;↵
}↵
if(rowsum == colsum)↵
{↵
if(isdiagonal1 && d1sum != rowsum)↵
{↵
no();↵
return 0;↵
}↵
if(isdiagonal2 && d2sum != rowsum)↵
{↵
no();↵
return 0;↵
}↵
ll value = commonsum - rowsum;↵
if(value > 0)↵
{↵
cout << value << '\n';↵
return 0;↵
}↵
else↵
{↵
no();↵
return 0;↵
}↵
}↵
else↵
{↵
no();↵
return 0;↵
}↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:711C]↵
↵
<spoiler summary="Code (O(nkm^2))">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int N = 101;↵
const int MOD = 1e9 + 7;↵
const ll INF = ll(1e18);↵
↵
ll dp[N][N][N];↵
int c[N];↵
ll cost[N][N];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n, m, k; cin >> n >> m >> k;↵
for(int i = 1; i <= n; i++)↵
{↵
cin >> c[i];↵
}↵
for(int i = 0; i <= n; i++)↵
{↵
for(int j = 0; j <= k; j++)↵
{↵
for(int a = 0; a <= m; a++)↵
{↵
dp[i][j][a] = INF;↵
}↵
}↵
}↵
for(int i = 1; i <= n; i++)↵
{↵
for(int j = 1; j <= m; j++)↵
{↵
cin >> cost[i][j];↵
}↵
}↵
if(c[1] == 0)↵
{↵
for(int i = 1; i <= m; i++)↵
{↵
dp[1][1][i] = cost[1][i];↵
}↵
}↵
else↵
{↵
dp[1][1][c[1]] = 0;↵
}↵
for(int i = 2; i <= n; i++)↵
{↵
for(int j = 1; j <= k; j++)↵
{↵
if(c[i] == 0)↵
{↵
for(int a = 1; a <= m; a++)↵
{↵
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);↵
for(int b = 1; b <= m; b++)↵
{↵
if(b != a) dp[i][j][a] = min(dp[i][j][a], dp[i-1][j-1][b] + cost[i][a]);↵
}↵
}↵
}↵
else↵
{↵
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);↵
for(int b = 1; b <= m; b++)↵
{↵
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);↵
}↵
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';↵
}↵
}↵
}↵
ll ans = INF;↵
for(int i = 1; i <= m; i++)↵
{↵
ans = min(ans, dp[n][k][i]);↵
}↵
if(ans >= INF) ans = -1;↵
cout << ans;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code (O(nkm))">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int N = 101;↵
const int MOD = 1e9 + 7;↵
const ll INF = ll(1e18);↵
↵
ll dp[N][N][N];↵
int c[N];↵
ll cost[N][N];↵
ll idx[N][N];↵
ll m1[N][N];↵
ll m2[N][N];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n, m, k; cin >> n >> m >> k;↵
for(int i = 1; i <= n; i++)↵
{↵
cin >> c[i];↵
}↵
for(int i = 0; i <= n; i++)↵
{↵
for(int j = 0; j <= k; j++)↵
{↵
m1[i][j] = INF; m2[i][j] = INF; idx[i][j] = -1;↵
for(int a = 0; a <= m; a++)↵
{↵
dp[i][j][a] = INF;↵
}↵
}↵
}↵
for(int i = 1; i <= n; i++)↵
{↵
for(int j = 1; j <= m; j++)↵
{↵
cin >> cost[i][j];↵
}↵
}↵
if(c[1] == 0)↵
{↵
for(int i = 1; i <= m; i++)↵
{↵
dp[1][1][i] = cost[1][i];↵
if(dp[1][1][i] <= m1[1][1])↵
{↵
if(dp[1][1][i] == m1[1][1])↵
{↵
idx[1][1] = -2;↵
}↵
else↵
{↵
idx[1][1] = i;↵
}↵
m2[1][1] = m1[1][1];↵
m1[1][1] = dp[1][1][i];↵
}↵
else if(dp[1][1][i] <= m2[1][1])↵
{↵
m2[1][1] = dp[1][1][i];↵
}↵
}↵
}↵
else↵
{↵
dp[1][1][c[1]] = 0;↵
m1[1][1] = 0; idx[1][1] = c[1];↵
}↵
for(int i = 2; i <= n; i++)↵
{↵
for(int j = 1; j <= k; j++)↵
{↵
if(c[i] == 0)↵
{↵
for(int a = 1; a <= m; a++)↵
{↵
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);↵
ll tmp = INF;↵
if(a == idx[i-1][j-1])↵
{↵
tmp = m2[i-1][j-1];↵
}↵
else↵
{↵
tmp = m1[i-1][j-1];↵
}↵
dp[i][j][a] = min(dp[i][j][a], tmp + cost[i][a]);↵
}↵
}↵
else↵
{↵
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);↵
for(int b = 1; b <= m; b++)↵
{↵
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);↵
}↵
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';↵
}↵
for(int a = 1; a <= m; a++)↵
{↵
if(dp[i][j][a] <= m1[i][j])↵
{↵
if(dp[i][j][a] == m1[i][j])↵
{↵
idx[i][j] = -2;↵
}↵
else↵
{↵
idx[i][j] = a;↵
}↵
m2[i][j] = m1[i][j];↵
m1[i][j] = dp[i][j][a];↵
}↵
else if(dp[i][j][a] <= m2[i][j])↵
{↵
m2[i][j] = dp[i][j][a];↵
}↵
}↵
}↵
}↵
ll ans = INF;↵
for(int i = 1; i <= m; i++)↵
{↵
ans = min(ans, dp[n][k][i]);↵
}↵
if(ans >= INF) ans = -1;↵
cout << ans;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:711D]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int INF = 1e9 + 7;↵
const int MOD = 1e9 + 7;↵
const int N = 1e6 + 3;↵
↵
int a[N];↵
int visited[N];↵
ll ans;↵
vector<int> cycles;↵
ll dp[N];↵
int cyclecnt;↵
↵
void dfs2(int u)↵
{↵
cycles[cyclecnt]++;↵
visited[u] = 3;↵
if(visited[a[u]] == 3) return ;↵
dfs2(a[u]);↵
}↵
↵
void dfs(int u)↵
{↵
visited[u] = 2;↵
if(visited[a[u]] == 0)↵
{↵
dfs(a[u]);↵
}↵
else if(visited[a[u]] == 1)↵
{↵
visited[u] = 1;↵
return ;↵
}↵
else↵
{↵
cycles.pb(0);↵
dfs2(u);↵
cyclecnt++;↵
}↵
visited[u] = 1;↵
}↵
↵
int main()↵
{↵
//ios_base::sync_with_stdio(0); cin.tie(0);↵
int n; scanf("%d", &n);↵
for(int i = 1; i <= n; i++)↵
{↵
scanf("%d", a + i);↵
}↵
dp[0] = 1;↵
for(int i = 1; i <= n; i++)↵
{↵
dp[i] = (dp[i-1]*2LL)%MOD;↵
}↵
ans = 1;↵
memset(visited, 0, sizeof(visited));↵
for(int i = 1; i <= n; i++)↵
{↵
if(visited[i] == 0)↵
{↵
dfs(i);↵
}↵
}↵
ll cnt = n;↵
for(int i = 0; i < cycles.size(); i++)↵
{↵
cnt -= cycles[i];↵
ans = (ans*(dp[cycles[i]]-2+MOD))%MOD;↵
}↵
ans = (ans*dp[cnt])%MOD;↵
if(ans < 0) ans += MOD;↵
int ans2 = ans;↵
printf("%d\n", ans2);↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:711E]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef vector<int> vi;↵
↵
const int MOD = 1e6 + 3;↵
↵
ll power(ll base, ll exp)↵
{↵
ll ans = 1;↵
while(exp)↵
{↵
if(exp&1) ans = (ans*base)%MOD;↵
base = (base*base)%MOD;↵
exp>>=1;↵
}↵
return ans;↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
ll n, k;↵
cin >> n >> k;↵
if(n <= 63 && k > (1LL<<n))↵
{↵
cout << 1 << " " << 1;↵
return 0;↵
}↵
ll v2 = 0;↵
int digits = __builtin_popcountll(k - 1);↵
v2 = k - 1 - digits;↵
ll ntmp = n % (MOD - 1);↵
if(ntmp < 0) ntmp += (MOD - 1);↵
ll ktmp = k % (MOD - 1);↵
if(ktmp < 0) ktmp += (MOD - 1);↵
ll v2tmp = v2 % (MOD - 1);↵
if(v2tmp < 0) v2tmp += (MOD - 1);↵
ll exponent = ntmp*(ktmp - 1) - v2tmp;↵
exponent %= (MOD - 1);↵
if(exponent < 0) exponent += MOD - 1;↵
ll denom = power(2, exponent);↵
ll numpart = 0;↵
if(k - 1 >= MOD)↵
{↵
numpart = 0;↵
}↵
else↵
{↵
ll prod = 1;↵
ll ntmp2 = power(2, ntmp);↵
prod = power(2, v2tmp);↵
prod = power(prod, MOD - 2);↵
if(prod < 0) prod += MOD;↵
for(ll y = 1; y <= k - 1; y++)↵
{↵
prod = (prod * (ntmp2 - y))%MOD;↵
}↵
numpart = prod;↵
}↵
ll num = (denom - numpart)%MOD;↵
num %= MOD; denom %= MOD;↵
if(num < 0) num += MOD;↵
if(denom < 0) denom += MOD;↵
cout << num << " " << denom;↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
The tutorial currently shows that it is unavailable for now. It will appear after system tests.
