10000 euro / Class Euro
Euclidean like algorithm
Board board.
[template] Euclidean algorithm
#include<bits/stdc++.h>
#define ll long long
#define N 22
#define P 998244353
ll t,p,q,r,l;
struct Po{
ll cntu,cntr,sumi,sums,sqrs,prod;
Po(){cntu = cntr = sumi = sums = sqrs = prod = 0;}
Po operator + (Po b) {
Po c;
c.cntu=(cntu+b.cntu)%P,c.cntr=(cntr+b.cntr)%P;
c.sumi=(sumi+b.sumi+cntr*b.cntr)%P;
c.sums=(sums+b.sums+cntu*b.cntr)%P;
c.sqrs=(sqrs+b.sqrs+((cntu*cntu)%P)*b.cntr+(2*cntu*b.sums)%P)%P;
c.prod=((prod+b.prod+((cntu*cntr)%P)*b.cntr)%P+cntu*b.sumi+cntr*b.sums)%P;
return c;
}
}nu,nr,ans;
inline Po pow(Po a,ll k){
Po res;
while(k){
if(k & 1){res = res + a;}
a = a + a;
k >>= 1;
}
return res;
}
inline ll div(ll a,ll b,ll c,ll d){return ((long double)1.0 * a * b + c) / d;}
inline Po solve(ll p,ll q,ll r,ll l,Po a,Po b){
if(!l)return Po();
if(p >= q)return solve(p % q,q,r,l,a,pow(a,p / q) + b);
ll m = div(l,p,r,q);
if(!m)return pow(b,l);
ll cnt = l - div(q,m,-r - 1,p);
return pow(b,(q - r - 1) / p) + a + solve(q,p,(q - r - 1) % p,m - 1,b,a) + pow(b,cnt);
}
int main(){
scanf("%lld",&t);
while(t -- ){
scanf("%lld%lld%lld%lld",&l,&p,&r,&q);
nu.cntu = 1,nu.cntr = nu.sumi = nu.sums = nu.sqrs = nu.prod = 0;
nr.cntu = nr.sums = nr.sqrs = nr.prod = 0,nr.sumi = nr.cntr = 1;
ans = pow(nu,r / q) + solve(p,q,r % q,l,nu,nr);
printf("%lld %lld %lld\n",(ans.sums+r/q)%P,(ans.sqrs+((r/q)%P)*((r/q)%P))%P,ans.prod);
}
}
Universal Euclid
Think of it as a \ (\ sum a^xb^y \) type.
Then you can write a matrix:
\(\begin{bmatrix}\sum_x a^xb^y\\a^xb^y\end{bmatrix}\)\(\begin{bmatrix}1&0\\0&b\end{bmatrix}\)\(\begin{bmatrix}1&a\\0&1\end{bmatrix}\)
Then write \ (a,b \) in matrix form
prime number
[template] Pollard Rho algorithm
First judge whether a number is a prime number, and use Miller Rabin test , otherwise use Pollard Rho algorithm Find a factor, recursive operations \ (n / p \) and \ (p \).
[template] Pollard Rho algorithm#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
long long max_factor, n;
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
long long quick_pow(long long x, long long p, long long mod) { //Counting
long long ans = 1;
while (p) {
if (p & 1) ans = (__int128)ans * x % mod;
x = (__int128)x * x % mod;
p >>= 1;
}
return ans;
}
bool Miller_Rabin(long long p) { //Judgement prime
if (p < 2) return 0;
if (p == 2) return 1;
if (p == 3) return 1;
long long d = p - 1, r = 0;
while (!(d & 1)) ++r, d >>= 1; //Treat d as odd
for (long long k = 0; k < 10; ++k) {
long long a = rand() % (p - 2) + 2;
long long x = quick_pow(a, d, p);
if (x == 1 || x == p - 1) continue;
for (int i = 0; i < r - 1; ++i) {
x = (__int128)x * x % p;
if (x == p - 1) break;
}
if (x != p - 1) return 0;
}
return 1;
}
long long Pollard_Rho(long long x) {
long long s = 0, t = 0;
long long c = (long long)rand() % (x - 1) + 1;
int step = 0, goal = 1;
long long val = 1;
for (goal = 1;; goal *= 2, s = t, val = 1) { //Multiplication optimization
for (step = 1; step <= goal; ++step) {
t = ((__int128)t * t + c) % x;
val = (__int128)val * abs(t - s) % x;
if ((step % 127) == 0) {
long long d = gcd(val, x);
if (d > 1) return d;
}
}
long long d = gcd(val, x);
if (d > 1) return d;
}
}
void fac(long long x) {
if (x <= max_factor || x < 2) return;
if (Miller_Rabin(x)) { //If x is prime
max_factor = max(max_factor, x); //Update answer
return;
}
long long p = x;
while (p >= x) p = Pollard_Rho(x); //Using this algorithm
while ((x % p) == 0) x /= p;
fac(x), fac(p); //Continue to decompose x and p downward
}
int main() {
scanf("%d", &t);
while (t--) {
srand((unsigned)time(NULL));
max_factor = 0;
scanf("%lld", &n);
fac(n);
if (max_factor == n) //The biggest prime factor is yourself
printf("Prime\n");
else
printf("%lld\n", max_factor);
}
return 0;
}
CF1334E Divisor Paths
Guess the conclusion.
If \ (a,b \) has a multiple relationship, it is always larger.
Otherwise, go to \ (gcd(a,b) \) first.
Min max tolerance and exclusion.
[HAOI2015] bitwise OR
Consider each in turn.
Set \ (a_k \) as the time when the \ (K \) bit is \ (1 \).
Find \ (E(\max(U))\)(\(U \) is the complete set).
Consider how to find \ (E(\min(U)) \).
Yes \ (\ sum v * P(v) \)
Let \ (P(S) \) be the probability of the selected set \ (S \), and \ (P'(S) \) be the probability of the selected set \ (S \).
Then the probability of \ (\ min(S) = k \) is that the subset of the complement of \ (S \) is selected the first time \ (k - 1 \), and the subset of the complement of \ (S \) cannot be selected the last time.
Then the probability of \ (\ min(S) \) is \ (P (k) = P '(s \ bigopus U) ^ {K - 1} (1 - p' (s \ bigopus U)) \)
Set \ (p '(s \ bigopus U)) = P \)
Then \ (E(\min(S)) = \sum_{k = 1}^{\infty} k * P(k) = (1 - p) \sum_{k = 1}^{\infty}k * p^{k - 1}\)
Offset subtraction \ ((1 - p)Sum = \frac{1}{1 - p} \)
So there are \ (E (\ min (s)) = \ frac {1} {1 - p '(s \ bigopus U)} \)
We asked for \ (P '(all sets) \).
Use DWT.
But I won't (blanch!).
Borrow cmd code.
#include<algorithm>
#include<cstdio>
#define Maxn 1100000
using namespace std;
int n;
double a[Maxn];
int siz[Maxn];
int main()
{
scanf("%d",&n);n=(1<<n);
for (int i=0;i<n;i++)scanf("%lf",&a[i]);
for (int len=1;len<n;len<<=1)
for (int p=0;p<n;p+=len+len)
for (int i=p;i<p+len;i++)
a[i+len]+=a[i];
double ans=0;
for (int i=1;i<n;i++){
siz[i]=siz[i>>1]+(i&1);
double sav=(1-a[i^(n-1)]);
if (sav<1e-8){puts("INF");return 0;}
sav=1/sav;
ans+=(siz[i]&1) ? -sav:sav;
}printf("%.10lf",-ans);
return 0;
}
Return to the world
Consider extending \ (Min - Max \) directly.
Then there are \ (ANS = \ sum_{t \ in s} (- 1) ^ {| t| - K} \ binom {t| - 1} {K - 1} e (min (T)) \)
It is found that its \ (O(2^n) \) cannot be counted directly.
Find its \ (m \leq 100000 \) and think about a \ (dp \) related to \ (m \).
Consider adding, \ (|T|\),\(E(min(T)) \), where \ (E(min(T)) \) and \ (\ sum_{i\in T}p_i \) are directly related.
Then it is directly designed into the state \ (f[i][j][k] \) represents the number of schemes with the first \ (I \), selected \ (J \), and \ (\ sum_{j\in T}p_i = k \).
Then transfer directly.
At this time \ (O(n^2m) \), you can get a good score of \ (70 \).
70 point code#include<bits/stdc++.h>
#define ll long long
#define N 1005
#define M 10005
#define mod 998244353
int n,ki,m;
ll f[2][N][M];
int p[N];
ll s[N],inv[N];
inline ll Pow(ll a,ll b){
ll ans = 1;
while(b){
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
inline ll C(int a,int b){
// std::cout<<a<<" "<<b<<" "<<s[a] * inv[b] % mod * inv[a - b] % mod<<std::endl;
if(a < b)return 0;
return s[a] * inv[b] % mod * inv[a - b] % mod;
}
ll ans = 0;
int main(){
std::memset(f,sizeof(f),0);
scanf("%d%d%d",&n,&ki,&m);
ki = n - ki + 1;
s[0] = 1;
for(int i = 1;i <= n;++i)
s[i] = i * s[i - 1] % mod;
inv[n] = Pow(s[n],mod - 2);
for(int i = n - 1;i >= 0;--i)
inv[i] = (inv[i + 1] * (i + 1)) % mod;
for(int i = 1;i <= n;++i)
scanf("%d",&p[i]);
f[1][0][0] = 1;
for(int i = 1;i <= n;++i){
int now = i & 1;
for(int j = 0;j <= n;++j)
for(int k = 0;k <= m;++k){
// std::cout<<i<<" "<<j<<" "<<k<<" "<<f[now][j][k]<<std::endl;
if(f[now][j][k]){
// puts("TO");
int to = (i + 1) & 1;
f[to][j][k] += f[now][j][k];
f[to][j][k] %= mod;
// std::cout<<"to"<<i + 1<<" "<<j<<" "<<k<<" "<<f[to][j][k]<<std::endl;
f[to][j + 1][k + p[i]] += f[now][j][k];
f[to][j + 1][k + p[i]] %= mod;
// std::cout<<"to"<<i + 1<<" "<<j + 1<<" "<<k + p[i]<<" "<<f[to][j + 1][k + p[i]]<<std::endl;
}
}
for(int j = 0;j <= n;++j)
for(int k = 0;k <= m;++k)
f[now][j][k] = 0;
}
for(int j = 1;j <= n;++j)
for(int k = 0;k <= m;++k)
if(f[(n + 1) & 1][j][k]){
// std::cout<<j <<" "<<k<<" "<<f[(n + 1) & 1][j][k]<<" "<<C(j - 1,ki - 1)<<" "<<Pow(k,mod - 2)<<" "<<Pow(k,mod - 2) * k % mod<<std::endl;
ans = (ans + (((((j - ki)) % 2 ? (-1 * C(j - 1,ki - 1) + mod): (C(j - 1,ki - 1))) * f[(n + 1) & 1][j][k] % mod) * Pow(k,mod - 2) % mod)) % mod;
}
std::cout<<ans * m % mod<<std::endl;
}
Considering this dp, there is no future for optimization.
We reduced the dimension of him and threw part of the whole persimmon into the equation.
Considering \ (k < = 11 \), the new dimension should be \ (K \).
Let \ (f {I, J} \) represent the sum of \ ((- 1) ^ {t | - K} \ binom {t | - 1} {K - 1} \) of the first \ (I \) items \ (\ sum {I \ in t} P _i = J \).
Consider if not selected \ (f[i][j] += f[i - 1][j] \)
If you choose, you have to think about something wrong \ (f[i][j + p[i]] = f[i - 1][j] + \delta \), so we have to think about what \ (\ delta \) is.
Number of disassembled combinations.
\((-1)^{|T| - k + 1} \binom{|T|}{k - 1} = (-1) ^ {|T| - k + 1}[\binom{|T|}{k - 2} + \binom{|T| - 1}{k - 1}]\).
Know \ (sum (- 1) ^ {| t | - K + 1} \ binom {t |} {K - 2} - \ sum (- 1) ^ {t | - K} \ binom {t | - 1} \)
We found that we only need to record one dimension \ (k \).
\(f [i] [J] [k] \), \ (\ sum {I \ in t} P _i = J \) weight \ (\ sum (- 1) ^ {t | - K} \ binom {t | - 1} {K - 1} \)
If forced \ (f_{i,j + p[i],k} = f_{i - 1,j,k - 1} + f_{i - 1,j,k} \)
\(f[0][0][0] = 1\).
100 points#include<algorithm>
#include<cstdio>
#include<map>
#define mod 998244353
#define MaxM 10050
#define mod 998244353
using namespace std;
long long f[MaxM][15],ans;
int n,kk,m,p[MaxM];
long long powM(long long a,long long t)
{
long long ans=1;
while(t){
if (t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int main()
{
scanf("%d%d%d",&n,&kk,&m);kk=n-kk+1;
for (int i=1;i<=n;i++)scanf("%d",&p[i]);
f[0][0]=1;
for (int i=1;i<=n;i++)
if (p[i])
for (int j=m-p[i];j>=0;j--)
for (int k=kk;k;k--)
f[j+p[i]][k]=(f[j+p[i]][k]+f[j][k-1]-f[j][k])%998244353;
for (int j=1;j<=m;j++)
ans=(ans+f[j][kk]*m%mod*powM(j,mod-2))%mod;
printf("%lld",(ans+mod)%mod);
return 0;
}
FWT/FMT
[template] fast Mobius / Walsh transform (FMT/FWT)
Board questions.
[template] fast Mobius / Walsh transform (FMT/FWT)#include<bits/stdc++.h>
#define ll long long
#define N (1 << 18)
#define mod 998244353
#define inv2 499122177
int n;
ll a[N],b[N],A[N],B[N];
inline void FWT_or(ll *f,int type){
for(int mid = 1;mid < n;mid <<= 1)
for(int block = mid << 1,j = 0;j < n;j += block)
for(int i = j;i < j + mid;++i)
f[i + mid] = (f[i + mid] + f[i] * type + mod) % mod;
}
inline void FWT_and(ll *f,int type){
for(int mid = 1;mid < n;mid <<= 1)
for(int block = mid << 1,j = 0;j < n;j += block)
for(int i = j;i < j + mid;++i)
f[i] = (f[i] + f[i + mid] * type + mod) % mod;
}
inline void FWT_xor(ll *f,int type){
for(int mid = 1;mid < n;mid <<= 1)
for(int block = mid << 1,j = 0;j < n;j += block)
for(int i = j;i < j + mid;++i)
{
ll x = f[i],y = f[i + mid];
f[i] = (x + y) % mod * (type == 1 ? 1 : inv2) % mod;
f[i + mid] = (x - y + mod) % mod * (type == 1 ? 1 : inv2) % mod;
}
}
inline void work(void (*FWT)(ll *f,int type)){
for(int i = 0;i < n;++i)a[i] = A[i],b[i] = B[i];
FWT(a,1),FWT(b,1);
for(int i = 0;i < n;++i)a[i] = a[i] * b[i] % mod;
FWT(a,-1);
for(int i = 0;i < n;++i)
std::cout<<a[i]<<" ";
puts("");
}
int main(){
scanf("%d",&n);
n = 1 << n;
for(int i = 0;i < n;++i)
scanf("%d",&A[i]),A[i] %= mod;
for(int i = 0;i < n;++i)
scanf("%d",&B[i]),B[i] %= mod;
work(FWT_or);work(FWT_and);work(FWT_xor);
}
determinant
[provincial joint examination 2020 volume a] homework question
Find the weight sum of all spanning trees of undirected graph.
The weight of a spanning tree is defined as:
\(val(T) = (\sum_{i = 1}^{n - 1}w_{e_i}) \times \gcd(w_{e1},w_{e2},......w_{e_{n - 1}}\ )\)
Consider that we directly invert first to remove the following conditions.
Then it's equivalent to enumerating the factors every time, adding the qualified edges to the matrix, and then.
Then we just need to ask how to get \ (\ sum_{i = 1}^{n - 1}w_{e_i}) \).
Considering that if it is the multiplication of edge power, I will never kill. Unfortunately, I can't take it.
Consider a second-order polynomial whose edge weight is \ (wx+1 \) and operates under membrane \ (x^2 \).
In the elimination, we can directly find the inverse.
The inverse of \ ((a+bx) \) of the second-order membrane \ (x^2 \) is \ ((a^{-1} - ba^{-2}x) \)
Expectation and probability
[ZJOI2020] Traditional Arts
Consider splitting contributions for each point.
Consider asking us to think about each additional operation, which is related to the final expectation of the previous \ (k - 1 \) times.
Each of our points maintains three states. Neither our ancestors nor our own have marks. We have marks, and our ancestors have marks.
If the ancestor has a tag, he will be tagged when accessing the sibling node.
If you have a tag, you will lose access to the nodes in the subtree.
If the node is accessed with coverage, it will be marked anyway.
There are five situations to consider:
Visit yourself, visit your ancestors, visit your sons, visit your brothers, ask if you don't pay.
[MtOI2019] Xiaoling's troubles
It's hard not to rain.
But it's still a good question.
Think about success every time.
We enumerate the elements that finally become the answer.
The probability of finding an element as the final element depends on the probability of the initial final element.
Let \ (p_i \) be the probability that there are \ (I \) target elements at this time, so that all elements become target elements.
Then there are \ (p_i = \frac{i(n - i)}{n(n - 1)}(p_{i - 1} + p_{i + 1}) + (1 - 2\frac{i(n - i)}{n(n - 1)})p_i\)
Easy to see \ (2p_i = p_{i - 1} + p_{i + 1} \)
So it is an arithmetic sequence.
Know \ (p_0 = 0,p_n = 1 \), so there is \ (p_i = \frac{i}{n} \)
Next, consider the expectation problem. Considering that \ (f_i \) is expressed as the expected number of steps when the number of final elements is \ (n \), first give the equation: \ (f_i = \frac{n(n - 1)}{2i({n - i})} + \frac{i - 1}{2i}f_{i - 1} + \frac{i + 1}{2i}f_{i + 1}\).
Consider what the probability we find is equivalent to.
Equal to its number in all success states.
We have the expected number of steps to transition from \ (f_i \) to other states is \ (\ frac{n(n - 1)}{2i({n - i})} \)
Consider that we will only transfer from \ (i \) to \ (i + 1 \) and \ (i - 1 \),
The probability ratio of successful transition is the proportion of the number in the state space under the condition of success. Considering that \ (i \) itself has a conditional probability of success, and the probability of transition to both sides is the same, the fixed coefficient is its.
Then the Gaussian elimination is directly carried out, and it is found that it can be eliminated linearly.
What a tumor.
[MtOI2019] Xiaoling's troubles#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 2010;
string str;
double f[maxn][maxn], s[maxn], ans;
int num[30], n;
int main() {
cin >> str;
while(cin >> ans);
n = str.length();
for(int i = 0; i < n; i++) num[str[i]-'A']++;
for(int i = 1; i <= n-1; i++) {
f[i][i-1] = (double)(i-1) / (2*i); f[i][i] = -1;
f[i][i+1] = (double)(i+1) / (2*i); s[i] = -(double)n*(n-1)/(2*i*(n-i));
}
f[n][n] = 1; s[n] = 0;
for(int i = 1; i <= n-1; i++) {
if(fabs(f[i+1][i]) < eps) continue;
double z = f[i+1][i] / f[i][i];
for(int j = i; j <= n; j++) f[i+1][j] -= z * f[i][j];
s[i+1] -= z * s[i];
}
for(int i = n; i > 1; --i) {
if(fabs(f[i-1][i]) < eps) continue;
double z = f[i-1][i] / f[i][i];
for(int j = i; j <= n; j++) f[i-1][j] -= z * f[i][j];
s[i-1] -= z * s[i];
}
ans = 0;
for(int i = 0; i <= 'Z'-'A'; i++)
if(num[i])
ans += (double)num[i] / n * s[num[i]] / f[num[i]][num[i]];
printf("%.1f\n", ans);
return 0;
}