Theo

XX小学

Theo
22天前
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int primes[50005], cnt;
bool flag[50005];
int mobius[50005], sum[50005];

void init(int n)
{
mobius[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!flag[i])
{
mobius[i] = -1;
primes[cnt++] = i;
}
for (int j = 0; primes[j] * i <= n; j++)
{
int t = primes[j] * i;
flag[t] = true;
if (i % primes[j] == 0)
{
mobius[t] = 0;
break;
}
mobius[t] = mobius[i] * -1;
}
}
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + mobius[i];
}
}

int main()
{
init(50004);
int q;
scanf("%d", &q);
while (q--)
{
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
a /= d;
b /= d;
int n = min(a, b);
ll ans = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
r = min(n, min(a / (a / l), b / (b / l)));
ans += (sum[r] - sum[l - 1]) * (ll)(a / l) * (b / l);
}
printf("%lld\n", ans);
}
return 0;
}



Theo
22天前
#include<bits/stdc++.h>
using namespace std;
const int N = 14;
const double INF = 1e20;
int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y)
{
double &v = f[a][b][c][d][x][y];
if(v >= 0)
{
return v;
}
int as = a + (x == 0) + (y == 0);
int bs = b + (x == 1) + (y == 1);
int cs = c + (x == 2) + (y == 2);
int ds = d + (x == 3) + (y == 3);
if (as >= A && bs >= B && cs >= C && ds >= D)
{
return (v = 0);
}
int sum = a + b + c + d + (x != 4) + (y != 4);
sum = 54 - sum;
if (sum <= 0)
{
return (v = INF);
}
v = 1;
if (a < 13)
{
v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
}
if (b < 13)
{
v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
}
if (c < 13)
{
v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
}
if (d < 13)
{
v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
}
if (x == 4)
{
double t = INF;
for (int i = 0; i < 4; i++)
{
t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
}
v += t;
}
if (y == 4)
{
double t = INF;
for (int i = 0; i < 4; i++)
{
t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
}
v += t;
}
return v;
}

int main()
{
cin >> A >> B >> C >> D;
memset(f, -1, sizeof(f));
double t = dp(0, 0, 0, 0, 4, 4);
if(t > INF / 2)
{
puts("-1.000");
}
else
{
printf("%.3lf\n", t);
}
return 0;
}



Theo
22天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL A[25];
LL n, m;
int down = 1;

int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1)
{
res = (LL)res * a % p;
}
a = (LL)a * a % p;
k >>= 1;
}
return res;
}

int C(LL a, LL b)
{
if (a < b) return 0;
int up = 1;
for (LL i = a; i > a - b; i--)
{
up = i % mod * up % mod;
}
return (LL)up * down % mod;
}

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
for (int j = 1; j <= n - 1; j++)
{
down = (LL)j * down % mod;
}
down = qmi(down, mod - 2, mod);
int res = 0;
for (int i = 0; i < 1 << n; i++)
{
LL a = m + n - 1, b = n - 1;
int sign = 1;
for (int j = 0; j < n; j++)
{
if (i >> j & 1)
{
sign *= -1;
a -= A[j] + 1;
}
}
res = (res + C(a, b) * sign) % mod;
}
cout << (res + mod) % mod << endl;
return 0;
}



Theo
23天前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll d, t, diff, n, m, p1, p2, s1, s2;

int main()
{
cin >> n;
ll c[n + 1];
for(int i = 1; i <= n; i++)
{
cin >> c[i];
}
cin >> m >> p1 >> s1 >> s2;
c[p1] += s1;
p2 = m;
c[0] = 0;
for(int i = 1; i <= n; i++)
{
if(i < m)
{
d += (m - i) * c[i];
}
if(i > m)
{
t += (i - m) * c[i];
}
}
diff = abs(d - t);
for(int i = 1; i <= n; i++)
{
if(i < m)
{
if(abs(d + (m - i) * s2 - t) < diff)
{
p2 = i;
diff = abs(d + (m - i) * s2 - t);
}
}
if(i > m)
{
if(abs(t + (i - m) * s2 - d) < diff)
{
p2 = i;
diff = abs(t + (i - m) * s2 - d);
}
}
}
cout << p2;
return 0;
}



Theo
23天前
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dta[1024], sum[1024], dp[1024][128];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> dta[i];
}
sort(dta + 1, dta + n + 1);
for(int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + dta[i];
}
for(int i = 1; i <= n; i++)
{
for(int wait  = 0; wait < m; wait++)
{
int curbus = dta[i] + wait;
if(wait)
{
dp[i][wait] = dp[i][wait - 1];
}
else
{
dp[i][wait] = curbus * i - sum[i];
}
for(int lastbus = max(curbus - 2 * m + 1, 0); lastbus <= curbus - m; lastbus++)
{
int lastcarry = lower_bound(dta + 1, dta + n + 1, lastbus + 1) - (dta + 1);
int lastwait = min(lastbus - dta[lastcarry], m - 1);
int tmp = dp[lastcarry][lastwait] + (i - lastcarry) * curbus - (sum[i] - sum[lastcarry]);
if(tmp < dp[i][wait])
{
dp[i][wait] = tmp;
}
}
}
}
cout << dp[n][m - 1];
return 0;
}



Theo
23天前
#include<bits/stdc++.h>
using namespace std;
#define maxn 105
int ans[maxn][maxn];
int color[maxn][maxn];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m;

void dfs(int currow, int curcol, int cost, bool magic)
{
if(cost >= ans[currow][curcol])
{
return;
}
ans[currow][curcol] = cost;
for(int i = 0; i < 4; i++)
{
int nextrow = currow + dir[i][0], nextcol = curcol + dir[i][1];
if(nextrow < 1 || nextcol < 1 || nextrow > m || nextcol > m)
{
continue;
}
if(!color[nextrow][nextcol])
{
if(magic)
{
color[nextrow][nextcol] = color[currow][curcol];
dfs(nextrow, nextcol, cost + 2, 0);
color[nextrow][nextcol] = 0;
}
}
else if(color[nextrow][nextcol] != color[currow][curcol])
{
dfs(nextrow, nextcol, cost + 1, 1);
}
else
{
dfs(nextrow, nextcol, cost, 1);
}
}
}

int main()
{
cin >> m >> n;
for(int i = 1; i <= n; i++)
{
int x, y, c;
cin >> x >> y >> c;
color[x][y] = c + 1;
}
memset(ans, 0x7f, sizeof(ans));
dfs(1, 1, 0, 1);
if(ans[m][m] == 0x7f7f7f7f)
{
cout << -1;
}
else
{
cout << ans[m][m];
}
return 0;
}



Theo
24天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin >> n;
int res = INT_MAX;
for (int i = 0; i < 3; i++)
{
int a, b;
cin >> a >> b;
res = min(res, (n + a - 1) / a * b);
}
cout << res << endl;
return 0;
}



Theo
26天前
#include<bits/stdc++.h>
using namespace std;
int water[105], a[10005];

int main()
{
while(1)
{
int *a = new int;
}
return 0;
}



Theo
27天前
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll get(int a, int b)
{
ll res = 1;
while (b--)
{
res *= a;
}
return res;
}

int main()
{
int n, k;
cin >> k >> n;
ll res = 0;
for (int i = 0; i < 20; i++)
{
if (n >> i & 1)
{
res += get(k, i);
}
}
cout << res << endl;
return 0;
}


Theo
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 35;

int n;
int a[N][N];

int gauss()
{
int r, c;
for (r = 1, c = 1; c <= n; c ++ )
{
int t = r;
for (int i = r + 1; i <= n; i ++ )
if (a[i][c])
t = i;
if (!a[t][c]) continue;
for (int i = c; i <= n + 1; i ++ ) swap(a[t][i], a[r][i]);
for (int i = r + 1; i <= n; i ++ )
for (int j = n + 1; j >= c; j -- )
a[i][j] ^= a[i][c] & a[r][j];
r ++ ;
}
int res = 1;
if (r < n + 1)
{
for (int i = r; i <= n; i ++ )
{
if (a[i][n + 1]) return -1;
res *= 2;
}
}
return res;
}

int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
memset(a, 0, sizeof a);
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i][n + 1]);
for (int i = 1; i <= n; i ++ )
{
int t;
scanf("%d", &t);
a[i][n + 1] ^= t;
a[i][i] = 1;
}

int x, y;
while (scanf("%d%d", &x, &y), x || y) a[y][x] = 1;

int t = gauss();
if (t == -1) puts("Oh,it's impossible~!!");
else printf("%d\n", t);
}

return 0;
}