Order according to the degree of difficulty (refer to the number of questions)

-J Circular Billiard Table

• Meaning Description: a small ball is shot from an edge of the disk at an angle of \ (\ alpha \) with the vertical direction. The small ball moves along the reflection law inside the disk. It is solved that the small ball collides several times before returning to the origin for the first time
• After analysis, we can see that the center angle of the small ball remains unchanged during the reflection process, and our center angle \ (\ theta=2\alpha \) is obvious, so we can know that when the small ball returns to the origin \ (n \) times, there must be \ (n\cdot\theta=k\cdot360 \), where \ (K \) is a positive integer
• So we need to solve the minimum \ (n \) that satisfies \ (360|n\theta \)
• To solve the minimum positive integer \ (n \) of \ (a|n*b \), we know that \ (n=\frac{a}{gcd(a,b)} \)
• It can be solved by substituting the numerical value into the above formula

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T,a,b;
int prime[1000005];
int cnt=0;
vector<int> ans;
int div(int x){
    for(int i=1;i<=cnt;i++){
        if(x==1)break;
        if(x%prime[i]){
            x/=prime[i];
            ans.push_back(prime[i]);
            i-=1;
        }
    }
}   


int main(){
    //cout<<__gcd(50,360)<<endl;
    cin>>T;
    while(T--){
        scanf("%lld %lld",&a,&b);
        ll x=b*180;
        // int i;
        // for(i=1;;i++){
        //     if(i*a % x==0)break;
        // }     
        // cout<<i-1<<endl;
        cout<<(x/__gcd(a,x))-1<<endl;
        
    }
    return 0;
}

-D Period

• Meaning Description: specify an integer \ (t \), if it is a \ (period \) of the string \ (s \), if and only if for any \ (i\in (T,|s 124] \), there are \ (s[i]=s[i-T] \) and \ (1\le T\le |s 124\), we give a character string containing only lowercase letters, and give \ (q \) queries. Each query modifies a position of the string to #, and the modifications are independent of each other, Find the number of \ (period \) strings under the current modification
• All the questions in this question have only one position change in the string. It is relatively easy to deal with the question content. We first preprocess the original string. Through the preprocessing results and modifying the position, we can get the answer to each question.
• Therefore, the key to this problem is how to preprocess. The \ (period \) in the problem naturally reminds us of the \ (kmp \) algorithm. We can first find the \ (next \) array of the original string, and then do further solution with the help of the \ (next \) array
• After obtaining the \ (next \) array, because the \ (I \) bit in the original string should correspond to the \ (i-1 \) bit in the \ (next \) array, the value of our initialization upper bound should be \ (j=len \), and then we continuously backtrack forward with the help of the number of \ (next \) to do \ (j=nex[j] \). For \ (next [J]! = 0 \), we can explain that there is a \ (period \) with a length of \ (next \)
• We make statistics on the occurrence of \ (nex[j] \) in the backtracking process. Finally, we calculate the prefix and array \ (a[i] \) to indicate how many \ (period \) the string has with a length within \ (I \)
• The letter of the current modification position \ (x \) is #. Obviously, the \ (period \) with a length greater than or equal to \ (x \) can no longer be called \ (period \), but because the length of \ (period \) is considered from both the team head element and the team tail element, we also need to consider from the team head and the team tail when limiting the length of \ (x \). We do \ (x=min(x-1,len-x) \), The obtained \ (x \) is obviously the upper limit length. Directly substituting into the array \ (a \) is the answer to the current query

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
char s[maxn];
int q,len;
int nex[maxn],a[maxn]; 
// aabaaba
// How to solve the period

void Getnext(){
    int j=0,k=-1;
    nex[0]=-1;
    while(j<=len-1){
        if(k==-1||s[j]==s[k]){
            j++;
            k++;
            nex[j]=k;
        }else{
            k=nex[k]; //Forward backtracking
        }
    }

}
void prenext(){
    int j=len;
    while(j>0){
        a[nex[j]]+=1;
        j=nex[j];
    }
    a[0]=0;
    for(int i=1;i<=len-1;i++){
        a[i]+=a[i-1];
    }
}

int main(){
    scanf("%s",s);
    len=strlen(s);
    Getnext();
    prenext();
    scanf("%d",&q);
    // Preprocess the string first
    // Query related operations are handled through array records
    for(int i=1;i<=len;i++){
        cout<<nex[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=len;i++){
        cout<<a[i]<<' ';
    }
    // cout<<nex[3]<<endl;
    // cout<<nex[len-1]<<endl;
    while(q--){
        int x;
        scanf("%d",&x);
        x=min(x-1,len-x);
        printf("%d\n",a[x]);
    }

    return 0;
}

-G Desserts

• There are \ (n \) items, and each item has \ (a[i] \) items. We need to distribute all these \ (n \) items to at most \ (m \) individuals, and each person can only take one item of each kind at most. Find the number of distribution schemes for each kind of people within the range \ ([1,m] \)
• Simple thought: it is easy to know that only when the number of people allocated is greater than the maximum number of items in \ (n \), can all products be fully allocated, so the number of schemes is not 0. At this time, for the \ (I \) product, we obviously have \ (C {t} ^{a [i]} \) allocation strategies, where \ (t \) is the current number of people, which meets \ (1\le t\le m \). At this time, we only need to multiply the allocation strategies of all products to get the total number of allocation schemes under the current number of people, and the time complexity is \ (O(mn) \), which will obviously timeout, So we need to think about how to optimize the time complexity
• Optimization (the hardest point to think of in this question): we notice that there are conditional \ (\ sum ^ n {I = 1} a _i \ Le 10 ^ 5 \) in the question, so we can know that for \ (n \) \ (a _i \), we can only have \ (\ sqrt{2*10^5} \) different \ (\ frac{n(n-1)}{2}\le10^5) \), and we can use \ (unordered\_set \) to record all different \ (a[i] \) and their occurrences, For multiple occurrences of \ (a[i] \), we can use the fast power algorithm. Finally, under different numbers of people, we can calculate and multiply the results of each \ (a_i '\) in \ (unordered\_set \) to obtain the final result.
• Reference code

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353 
#define ll long long
const int maxn = 5e4+5;
const int M = 1e5+5;
int n,m;
int a[maxn],cnt[maxn]; // The latter is used to record a_i number of occurrences of the same number 
unordered_set<int> at; // Used to record the a array after de duplication

// Violent enumeration O(nm) obviously timed out
// So the key to this problem is how to calculate quickly

ll exp(ll a,ll b){
    ll tmp=1;
    while(b){
        if(b&1)tmp=(a*tmp)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return tmp%mod;
}


ll fac[M],finv[M];
ll inv(ll x){
    return exp(x,mod-2);
}
int init(){
    fac[0]=1;
    for(int i=1;i<=M-5;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    finv[M-5]=inv(fac[M-5]);
    for(int i=M-6;i>=0;i--){    
        finv[i]=finv[i+1]*(i+1)%mod;
    }
}

ll C(ll n,ll m){ // Fast calculation
    if(m>n)return 0;
    return fac[n]*finv[m]%mod*finv[n-m]%mod;
}

int main(){
    init();
    cin>>n>>m;
    int maxx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxx=max(maxx,a[i]);
    }
    for(int i=1;i<=n;i++){
        cnt[a[i]]++;
        at.insert(a[i]);
    }
    for(int i=1;i<=m;i++){
        if(i<maxx){ // Cannot fully allocate
            printf("0\n");
            continue;
        }
        ll ans=1;
        for(auto x:at){
            ans=(ans*exp(C(i,x),cnt[x]))%mod;
        }
        printf("%lld\n",ans); // Large output, use printf
    }
    return 0;
}