2022 Niuke multi school second CDE

C topic
The question ：nim game , If you win first , Try to win fast , If you lose, try to lose slowly .
Ask for the most games , And the number of optimal strategies executed first
Here are two conclusions ：
1, Stone number XOR and sum is 0 Words , Defeat first , Otherwise win
2, If you lose first , It can be constructed that only one stone is taken from the back of the hand .
Conclusion 1 Prove slightly .
Conclusion 2
If you start, you'll lose , in other words xor_sum=0
First consider the scheme of constructing as many games as possible , First in lowbit Take one from the smallest pile of stones .
The hindhand can only be symmetrically on the other lowbit Take one from the same heap . For example, the first one is …100, After taking it, it becomes …011,xor_sum->xor_sum^(111), The hindhand must construct (111) Offset the impact . If you choose lowbit Bigger than the first lowbit A pile of , Then it will affect the higher position . So the backhand can only choose lowbit A pile of stones , Take a stone . In other words, the second hand is operated symmetrically with the first hand , Go symmetrically lowbit An equal pile of stones .
A scheme is constructed above , Make the number of the General Administration sum, Then consider the number of schemes taken in the first step in the above case
Arrange the conditions again , Now you can only take one first , To make the hindhand can only take one . We consider what circumstances , The hindhand can take more . Set up a pile of stones taken by hand lowbit It's No i position , If there is another pile i Position as 1 And i Not for lowbit, Then the hindhand can take more . For example, take it first 10100, There is 00110, Take it first and then xor_sum->xor_sum^(111), The back hand can handle two 1 Take it out and offset it (111) Influence .
Other situations ：
1, The first i Position as 0, So how to operate so that you can't offset the pair caused by the first hand i The influence of position .
2, The first i Position as 1 And for lowbit, Then the hindhand can only take a stone symmetrically ...
Certificate completion （ Disordered evidence ）

Now consider winning first , The first step is to take as many as possible , And leave XOR and as 0. How to find the maximum and how much to take away .
Let the original XOR and be S, From you to ai Middle selection t Remove a stone , XOR and 0.
Deduct it first ai, Then XOR and are S^ai, as long as ai>(S ^ ai) There is ,t = ai - (S ^ ai), bring S ^ (ai -t)=0.
maintain t And times .
very nb Thinking about the problem ！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x7f7f7f7f7f7f7f7f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int N=5e5+5;
const int mod=1e9+7;
const double eps=1e-8;
int n;
int a[N];
map<int,int> mp;
void solve(){
    
    cin>>n;
    int x_sum=0,sum=0;
    _for(i,1,n){
    
        cin>>a[i];
        x_sum ^= a[i];
        sum += a[i];
    }
    if( !x_sum ){
    
        int cnt=0;
        _for(i,1,n) mp[a[i]&-a[i]] = 0;
        _for(i,1,n){
    
            int t = a[i];
            t -= t&-t;
            while( t ){
    
                mp[t&-t]=1;
                t -= t&-t;
            }
        }
        _for(i,1,n) if( !mp[a[i]&-a[i]] ) cnt++;
        cout<<sum<<" "<<cnt<<endl;
    }
    else {
    
        int mx = 0,cnt=0;
        _for(i,1,n){
    
            if( a[i] > (a[i]^x_sum) ){
    
                int t = a[i] - (a[i]^x_sum);
                if( t > mx  ){
    
                    mx = t;
                    cnt=1;
                }
                else if( mx == t ) cnt++;
            }
        }
        cout<<sum-mx+1<<" "<<cnt<<endl;
    }
}
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif 
    IOS;
    int T;cin>>T;
    while(T--) solve();
    AC; 
}

D topic
The question ： to n The exchange relationship between items (n<=1e3), The exchange relationship is as follows a individual x It can be changed wb individual y, among w It's required , For the biggest w, These items cannot be exchanged without restrictions .（ Unrestricted exchange means 1 individual x in 2 individual y,1 individual y Can change 10 individual x, This allows unlimited Exchange ）
practice ： Consider drawing , Two points w, then check, The marginal weight is the exchange rate , Because the product is very large , Choose the right side right , Then it is to judge whether there is a positive ring

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x7f7f7f7f7f7f7f7f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define double long double
const int N=1e3+5;
const int mod=1e9+7;
const double eps=1e-8;
int n,m;
int vis[N],cnt[N];
double dis[N];
std::vector< pair<int,double> > G[N];
queue<int> q;
bool ck(double mid,int st){
    // Namely spaf Find the shortest path 
    mst(dis,0);
    mst(cnt,0);
    queue<int> q;
    _for(i,1,n){
    
        q.push(i);
        vis[i]=1;
    }
    while( !q.empty() ) {
    
        int x = q.front();q.pop();
        vis[x] = 0;
        for(auto [y,len] :G[x]){
    
            if( dis[x] + len + mid >  dis[y] ){
    
                dis[y] = dis[x] + len + mid;
                cnt[y]++;
                if( cnt[y] >= n ) return 0;
                if( !vis[y] ){
    
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
    return 1;
}
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif 
    // IOS;
    cin>>n>>m;
    _for(i,1,m){
    
        int b,d;
        double a,c;
        cin>>a>>b>>c>>d;
        G[b].push_back( {
    d,log2(c) - log2(a)});
    }
    double l = 0 , r = 1;
    _for(i,1,50){
    
        double mid = (l+r)/2;
        if( ck(log2(mid),1) ) l = mid;
        else r = mid;
    }
    printf("%.8Lf\n",r);
    AC; 
}

e topic
The question ： Long for n, contain k individual “bit” Number of strings , Output k from 0 To n Number of alternatives ,n<=1e6
practice ： Binomial inversion + Differential convolution
Consider tolerance and exclusion , set up $G_k$ Denotes containing k individual bit Number of alternatives ,$F_k$ At least k individual bit Number of alternatives
$F_k=C_{n-2k}^k\ast (26^n-3k)$
$G_k={\sum }_{j=k}^n(-1{)}^{j-k}\ast C_j^k{F}_j$, The separation coefficient after the expansion of the combination number
$k!\ast G_k={\sum }_{j=k}^n(j!F_j)\ast \frac{(-1{)}^{j-k}}{(j-k)!}$
It is found that the right side is the difference convolution form , Flip one of the polynomials and find convolution .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x7f7f7f7f7f7f7f7f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int maxn = 6e6+10;
const int p = 998244353;
int Pow(int x,int d){
    
    int tans = 1;
    if(d == 0)return 1%p;
    int a = Pow(x,d/2);
    tans = 1ll*a*a%p;
    if(d%2)tans = 1ll*tans*x%p;
    return tans%p;
}
typedef vector<int> Poly;// Polynomial definition 
int F1[maxn],F2[maxn];
int rev[maxn];
void NTT(int * A,int lim,int opt) {
    
    int i, j, k, m, gn, g, tmp;
    for(int i = 0; i < lim; ++i)rev[i] = (i & 1)*(lim >> 1) + (rev[i >> 1] >> 1);
    for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
    for(m = 2; m <= lim; m <<= 1) {
    
        k = m >> 1;
        gn = Pow(3,(p - 1) / m);
        for(i = 0; i < lim; i += m) {
    
            g = 1;
            for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
    
                tmp = 1ll * A[i + j + k] * g % p;
                A[i + j + k] = (A[i + j] - tmp + p) % p;
                A[i + j] = (A[i + j] + tmp) % p;
            }
        }
    }
    if(opt == -1){
    
        reverse(A+1,A+lim);
        int inv = Pow(lim,p-2);
        for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
    }
}
Poly mul(const Poly & A,const Poly & B){
    
    int n = A.size(),m = B.size();
    int siz = n + m - 1;
    Poly C(siz);
    if(siz < 64){
    // Less than or equal to 64 Direct violence counts 
        for(int i = 0;i < n;i++){
    
            for(int j = 0;j < m;j++)C[i+j] = (C[i+j] + 1LL*A[i]*B[j]%p)%p;
        }
        return C;
    }
    int fsiz = 1;
    while(fsiz <= siz)fsiz *= 2;
    for(int i = 0;i < fsiz;i++)F1[i] = F2[i] = 0;
    for(int i = 0;i < n;i++)F1[i] = A[i];
    for(int i = 0;i < m;i++)F2[i] = B[i];
    NTT(F1,fsiz,1);
    NTT(F2,fsiz,1);
    for(int i = 0;i < fsiz;i++)F1[i] = 1ll*F1[i]*F2[i]%p;
    NTT(F1,fsiz,-1);
    for(int i = 0;i < siz;i++){
    
        C[i] = F1[i];
    }
    return C;
}
const int N = 1e6+10;
ll qsm(int a,int b){
    
    int ans=1,tmp = a;
    while( b ){
    
        if( b&1 ) ans = (ans * tmp)%p;
        tmp = (tmp * tmp)%p;
        b>>=1;
    }
    return ans;
}
int fac[N],ni_f[N];
void ini(){
    
    fac[0]=1;
    int maxn = 1e6;
    _for(i,1,maxn) fac[i] =  (fac[i-1] * i)%p;
    ni_f[maxn] = qsm(fac[maxn],p-2);
    _rep(i,maxn-1,0) ni_f[i] = ni_f[i+1] * (i+1)%p;
}
ll C(int n,int m){
    
    if( m==n || m==0 ) return 1;
    if( n < m ) return 0;
    return fac[n] * ni_f[n-m]%p * ni_f[m]%p;
}
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif 
    IOS;
    ini();
    int n;
    cin>>n;
    Poly f(n+1,0);
    _for(i,0,n){
    
        if( n-3*i < 0  ) break;
        f[i] = qsm(26,n-3*i)*C(n-2*i,i)%p*fac[i]%p;
    }
    Poly g(n+1,0);
    _for(i,0,n){
    
        int flag = ((n-i)&1)?-1:1;
        g[i] = (p + flag*ni_f[n-i])%p;
    }
    Poly h = mul(f,g);
    _for(i,n,2*n) cout<<h[i]*ni_f[i-n]%p<<" ";
    AC;

}