Nguyên lý bù trừ mở rộng

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

template <class T> T gcd (T a, T b) {  while (b) { T r = a % b; a = b; b = r; } return a; }
template <class T> T lcm (T a, T b) { return a / gcd (a, b) * b; }

//long long sum=0;
//long long  num;

ll solve(vector<long long> & v, ll n){
int N=v.size();
ll sum=0;
ll num=n;
for(int i=1;i<(1<<N);i++){
    ll ct=1;
    for(int k=0;k<N;k++)if( i & (1<<k) ) ct=lcm(ct,v[k]);
        if(1 & __builtin_popcount(i))sum+=num/ct;
            else sum-=num/ct;
        }
        return sum;
    }

int main(){
    vector<long long> v;
    ll n,P,x;
   /* cin>>num;
    solve(v);
    ll res=gcd(sum,num);
    cout<<sum/res<<' '<<num/res;
    return 0;*/
    int t;
    cin>>t;
    while(t--){
       cin>>n>>P;
//       sum=0;
       for(int i=0;i<P;i++) {cin>>x ; v.push_back(x);}
       ll res=solve(v,n);
      // ll res=gcd(sum,n);
       cout<<res<<'\n';
       v.clear();
    }
    }

Nguyên lý bù trừ (Inclusion-Exclusion)

Đề bài: Cho số n, in ra số các số trong đoạn [1;n] chia hết cho 1 trong 4 số: 2,3,11,13.
Lời giải:
#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <class T> T gcd (T a, T b) {  while (b) { T r = a % b; a = b; b = r; } return a; }
template <class T> T lcm (T a, T b) { return a / gcd (a, b) * b; }

long long sum=0;
long long  num;

void solve(vector<long long> & v){
int N=v.size();

for(int i=1;i<(1<<N);i++){
    ll ct=1;
    for(int k=0;k<N;k++)if( i & (1<<k) ) ct=lcm(ct,v[k]);
        if(1 & __builtin_popcount(i))sum+=num/ct;
            else sum-=num/ct;
        }
    }

int main(){
    vector<long long> v={2,3,11,13};
    cin>>num;
    solve(v);
    ll res=gcd(sum,num);
    cout<<sum/res<<' '<<num/res;
    return 0;
    }

(a^b)%c

long long power(long long x,int y)
{
    if (!y)
    return 1;
    long long ret=power(x,y/2);
    ret=(ret*ret)%mod;
    if (y%2)
    ret=(ret*x)%mod;
    return ret;
}

P.Q^(-1) mod 1e9+7

Fermat’s little theorem

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a ^p – a is an integer multiple of p.

Here p is a prime number
a^p ≡ a (mod p).

Special Case: If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that a ^p-1-1 is an integer multiple of p.

a^p-1 ≡ 1 (mod p)
OR
a^p-1 % p = 1
Here a is not divisible by p.

Take an Example How Fermat’s little theorem works
Examples:

 P = an integer Prime number   
 a = an integer which is not multiple of P  
 Let a = 2 and P = 17 
 
 According to Fermat's little theorem 
  2 17 - 1     ≡ 1 mod(17)
 we got  65536 % 17 ≡ 1   
 that mean (65536-1) is an multiple of 17 

Use of Fermat’s little theorem
If we know m is prime, then we can also use Fermats’s little theorem to find the inverse.
a^m-1 ≡ 1 (mod m)
If we multiply both sides with a-1, we get
a^-1 ≡ a ^m-2 (mod m)
Below is the Implementation of above

filter_none edit
play_arrow
brightness_4

// C++ program to find modular inverse of a // under modulo m using Fermat's little theorem. // This program works only if m is prime. #include <bits/stdc++.h> using namespace std;    // To compute x raised to power y under modulo m int power(int x, unsigned int y, unsigned int m);    // Function to find modular inverse of a under modulo m // Assumption: m is prime void modInverse(int a, int m) {     if (__gcd(a, m) != 1)         cout << "Inverse doesn't exist";        else {            // If a and m are relatively prime, then         // modulo inverse is a^(m-2) mode m         cout << "Modular multiplicative inverse is "              << power(a, m - 2, m);     } }    // To compute x^y under modulo m int power(int x, unsigned int y, unsigned int m) {     if (y == 0)         return 1;     int p = power(x, y / 2, m) % m;     p = (p * p) % m;        return (y % 2 == 0) ? p : (x * p) % m; }    // Driver Program int main() {     int a = 3, m = 11;     modInverse(a, m);     return 0; }

Output :

Modular multiplicative inverse is 4

Bài A - Codeforces Beta Round #72 (Div.1 Only)

Valera rất quan tâm đến phép thuật. Phép thuật thu hút anh ta đến mức anh ta nhìn thấy nó ở khắp mọi nơi. Ông giải thích bất kỳ hiện tượng kỳ lạ và kỳ lạ nào thông qua sự can thiệp của các thế lực siêu nhiên.
   Valera hoàn toán vô tình có được một mảnh giấy da cổ, trên đó có một dãy số được viết. Anh ta nghĩ rằng những con số trong mảng này không phải là ngẫu nhiên. Kết quả của nghiên cứu sâu rộng Valera đã tìm ra một tính chất tuyệt vời mà một mảng ma thuật nên có: có một mảng được định nghĩa là ma thuật nếu tối  thiểu và tối đa trùng khớp.
 Anh ấy quyết định chia sẻ khám phá nổi bật với bạn, nhưng anh ấy nhờ bạn giúp đỡ để đáp lại. Mặc dù có trí thông minh và trí thông minh to lớn, Valera tính rất tệ và vì vậy bạn sẽ phải hoàn thành công việc của mình. Tất cả những gì bạn phải làm là đếm số lượng các phép thuật con của mảng số gốc, được viết trên giấy da. Subarray được định nghĩa là chuỗi không trống của các phần tử liên tiếp.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (1<=n<=10^5). Dòng thứ hai chứa một mảng các số nguyên a(1),a(2),...,a(n).
Đầu ra:
+ In ra một dòng duy nhất là câu trả lời của bài toán: số lượng mảng con, thỏa mãn mảng đó là ma thuật.
Ví dụ:
Đầu vào:
4
2 1 1 4
Đầu ra:
5
Đầu vào:
5
-2 -2 -2 0 1
Đầu ra:
8
Giải thích:
Ở ví dụ đầu tiên: [1;1],[2;2],[3;3],[4;4],[2;3]
Ở ví dụ thứ hai: [1;1],[2;2],[3;3],[4;4],[5;5],[1,2],[2,3],[1,3].
Hướng dẫn:
Lời giải:

#include<iostream>
long long n,S,r,p=2e9,x;
main(){
  for(std::cin>>n;std::cin>>x;S+=++r)if(x!=p)r=0,p=x;
  std::cout<<S;
}

Bài C - Codeforces Beta Round #1

Bài C:
Đề bài:
  Ngày nay tất cả các rạp xiếc ở Berland đều có một đấu trường với đường kính 13 mét, nhưng trong mọi thứ thì khác.
  Trong các đấu trường Berland cổ đại trong các rạp xiếc được định hình là một đa giác (tam giác) đều, kích thước và số lượng góc có thể thay đổi tử rạp xiếc này đến rạp xiếc khác. Ở mỗi góc của đấu trường có một cây cột đặc biệt, và sợi dây được căng giữa các cây cột đánh dấu các cạnh của đấu trường.
  Gần đây, các nhà khoa học từ Berland đã phát hiện ra phần còn lại của đấu trường xiếc cổ đại. Họ chỉ tìm thấy ba cây cột, những cái khác đã bị thời gian pháy hủy.
  Bạn được cho các tọa độ của ba cây trụ. Tìm ra giá trị nhỏ nhất của đấu trường có thể.
Đầu vào:
+ Đầu vào gồm 3 dòng, mỗi dòng là một cặp số - tọa độ của các cột. Bất kì tọa độ nào cũng không quá 1000 by absolute value, và được cho nhiều nhất 6 chữ số sau hàng thập phân.
Đầu ra:
+ In ra diện tích nhỏ nhất có thể của đầu trường cổ. Con số này chính xác tới ít nhất 6 số phần thập phân.
Ví dụ:
Đầu vào:
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000
Đầu ra:
1.00000000
Hướng dẫn:
 Các điểm có thể là các đỉnh của N- đa giác đều khi và chỉ khi với mỗi cặp, sự khác biệt của các góc cực của chúng (khi nhìn từ tâm đa giác) của 2*pi/N. Tất cả các điểm nằm trên đường tròn với cùng tâm với đa giác. Chúng ta có thể xác định vị trí trung tâm của đa giác / vòng tròn [nhưng chúng ta có thể tránh điều này, vì một hợp âm như giả sử, (x(1),y(1))-(x(2),y(2))] được nhìn thấy ở góc lớn hơn gấp đôi so với tâm điểm khác của một điểm khác của đường tròn (x(3),y(3))]
 Có nhiều cách để xác định vị trí trung tâm của vòng tròn, cách tôi đã xây dựng là xây dựng trung điểm vuông góc với các phân đoạn (x1,y1)-(x2,y2) và (x2,y2)-(x3,y3) ở dạng y=a*x+b và tìm giao điểm của chúng. Công thức y=a*x+b có nhược điểm là không thể sử dụng nếu đường thẳng song song với y, cách giải quyết có thể là xoay tất cả các điểm theo góc ngẫu nhiên (sử dụng công thức xl=x*cos(a)-y*sin(a),y'=y*cos(a)+x*sin(a)) cho đến khi không có đoạn nào nằm ngang (và do đó không có đường vuông góc nào là dọc).
  Sau khi biết tọa độ của tâm, chúng ta sử dụng hàm ưa thích: , trả về góc trong phần tư phải: a[i]=atan2(y[i]-ycenter,x[i]-xcenter) atan2.
  Diện tích của đa giác đều tăng khi tăng N, do đó có thể chỉ cần lặp qua tất cả các giá trị có thể có trên N theo thứ tự tăng dần và thoát khỏi chu kỳ khi tìm thấy N thỏa mãn đầu tiên.
 Sử dụng sin(x) là làm cho nó dễ dàng: sin(x)=0 khi x là bội của pi. Vì vậy, đối với các điểm thuộc về đa giác N, đa giác N đều.
sin(N*(a[i]-a[j])/2)=0.
 Bởi vì số học chính xác hữu hạn, fabs(sin(N*(a[i]-a[j])/2)).
Lời giải:

#include<cstdio>
#include<cmath>
#define D double
#define S(x) ((x)*(x))
#define G(t) a[t]=x[t]-x[2];b[t]=y[t]-y[2];c[t]=(S(x[t])+S(y[t])-S(x[2])-S(y[2]))/2;
#define M(p,q) (p[0]*q[1]-p[1]*q[0])
D g(D a,D b){return fabs(b)<1e-4?a:g(b,fmod(a,b));}
D x[3],y[3],a[3],b[2],c[2],A,X,Y;
int main()
{
for(int i=0;i<3;++i)scanf("%lf%lf",x+i,y+i);
G(0);G(1);
X=M(c,b)/M(a,b);
Y=M(a,c)/M(a,b);
for(int i=0;i<3;++i)a[i]=atan2(x[i]-=X,y[i]-=Y);
A=g(M_PI*2,g(fabs(a[1]-a[0]),fabs(a[2]-a[0])));
printf("%lf\n",(S(x[0])+S(y[0]))*sin(A)*M_PI/A);
}

Bài E - Codeforces Round 62 (Div.2)

Bài E:
Đề bài: Chúng ta kí hiệu rằng một mảng b nào đó là tồi tệ nếu nó chứa một mảng con b(l),b(l+1),...,b(r) với độ dài lẻ và lớn hơn 1 (l<r và r-l+1 là số lẻ) thỏa mãn $\forall i\in \left\{0,1,...,r-l\right\} b_{l+i}=b_{r-i}$.
Nếu một mảng không xấu, thì đó mảng tốt.
Bây giờ bạn được cho một mảng a(1),a(2),...,a(n). Một vài phần tử được thay thế bằng -1. Tính số mảng tốt bạn có thể đạt được bằng cách thay mỗi số -1 bằng 1 số nguyên nào đó từ 1 đến k.
Bởi vì câu trả lời có thể rất lớn, in ra nó modulo 998244353
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên n và k (2<=n,k<=2.10^5) - chiều dài của mảng a và kích thước của "alphabet"
+ Dòng thứ 2 chứa n số nguyên a(1),a(2),...,a(n) (a(i)=-1 hoặc 1<=a(i)<=k)- mảng a.
Đầu ra:
In ra một số nguyên - số mảng tốt bạn có thể đạt được , modulo 998244353.
Ví dụ:
Đầu vào:
2 3
-1 -1
Đầu ra:
9
/**/
Đầu vào:
5 2
1 -1 -1 1 2
Đầu ra:
0
/**/
Đầu vào:
5 3
1 -1 -1 1 2
Đầu ra: 2
/**/
Đầu vào:
4 200000
-1 -1 12345 -1
Đầu ra:
735945883.
Hướng dẫn:
 Đầu tiên, mảng chứa một mảng con đối xứng >=3 tương đương với mảng chứa một mảng con đối xứng có độ dài là 3.
Vì vậy, chúng ta cần tính số mảng mà không đối xứng có độ dài là 3. Điều này tương đương với mảng mà a[i]#a[i+2] với mọi i hợp lý.
Chú ý ràng, i và i+2 có cùng tính chẵn lẽ, vì vậy tất cả vị trí lẻ và vị trí chẵn trong mảng độc lập nhau, và câu trả lời là tích các cách chọn các số ở vị trí lẻ, và số cách chọn các số ở vị trí chẵn.
Về mặt tương đương hình thái điều kiện, a[i]#a[i+1] và chúng ta cần tính tất cả các cách để thay các số -1 bằng một cách nào đó các cặp phần tử liên tiếp là khác nhau.
  Để tính nó, chúng ta hãy nhìn vào chuỗi các số (-1) liên tiếp. Họ sẽ thấy rằng a,-1,-1,...,-1,b với l số (-1), ở đây a và b là các số nguyên dương (trường hợp a ở đây không có thể xét như k.(a,-1,-1,...,b với l-1 số -1)), trường hợp b rỗng được giải theo cách tương tự.
  Cuối cùng chúng ta cần tính số các dãy như vậy. Có hai loại dãy chúng ta cần xét tới đó là a,-1,..,-1,a (đầu và cuối giống nhau) và a,-1,-1,...,-1,b (đầu và cuối khác nhau). Giá trị chính xác của a và b không phải là vấn đề.
  Chúng ta sẽ tìm hai giá trị (đặt tên chúng là cntSame và cntDiff) với l số (-1) liên tiếp với thời gian O(log(l)). Các giá trị cơ sở: cntSame(0)=0,cntDiff(0)=1.
  Chúng ta thử chọn giá trị của -1 nằm ở giữa của dãy : Nếu l mod 2=1, thì chúng ta có thể tách thành hai dãy có độ dài [l/2] và cntSame(l)=cntSame(l/2)^2+(k-1).cntDiff(l/2)^2 và cntDiff(l)=2.cntSame(l/2).cntDiff(l/2)+(k-2).cntDiff(l/2)^2.
Nếu l mod 2= 1thì chỉ cần lặp giá trị cuối cùng -1m thì cntSame(l)=(k-1).cntDiff(l-1) và cntDiff(l)=cntSame(l-1)+(k-2).cntDiff(l-1).
Độ phức tạp cuối cùng là O(n).
Lời giải:

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = 998244353;
int norm(int a) {
    while(a >= MOD) a -= MOD;
    while(a < 0) a += MOD;
    return a;
}
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}

int n, k;
vector<int> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);
    fore(i, 0, n)
        cin >> a[i];
    return true;
}

pair<int, int> calc(int len) {
    if(len == 0) return {0, 1};
    if(len & 1) {
        auto res = calc(len >> 1);
        return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
                norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
    }
    auto res = calc(len - 1);
    return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
}

vector<int> curArray;

int calcSeg(int l, int r) {
    if(r >= sz(curArray)) {
        int len = r - l - 1, cf = 1;
        if(l < 0)
            len--, cf = k;
        if(len == 0) return cf;

        auto res = calc(len - 1);
        return mul(cf, norm(res.x + mul(k - 1, res.y)));
    }
    if(l < 0) {
        if(r - l == 1) return 1;
        auto res = calc(r - l - 2);
        return norm(res.x + mul(k - 1, res.y));
    }
    auto res = calc(r - l - 1);
    return curArray[l] == curArray[r] ? res.x : res.y;
}

inline void solve() {
    int ans = 1;
    fore(k, 0, 2) {
        curArray.clear();
        for(int i = 0; 2 * i + k < n; i++)
            curArray.push_back(a[2 * i + k]);

        int lst = -1;
        fore(i, 0, sz(curArray)){
            if(curArray[i] == -1) continue;
            ans = mul(ans, calcSeg(lst, i));
            lst = i;
        }
        ans = mul(ans, calcSeg(lst, sz(curArray)));
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}