The 2021 ICPC ASIA Taipei Regional programming contest L. leadfoot (combinatorics /2-adic assignment function +kummer theorem)

subject

The meaning of this topic depends on the topic

The number of drivers is unknown , Each driver initially wins 0 game , transport 0 game ,

Two drivers who currently win and lose the same number of games , Will play a game together ,

After the competition , The number of games won by one of the drivers +1, The number of games lost by the other driver +1,

The driver thought he won in total n site , Or lose in total m No more games after the game ,

You want to invite the least number of drivers , So that everyone can win in total n site , Or lose altogether m site ,

among , Win. 0 site 、 lost m The driver of the field will be awarded Leadfoot badges,

k(k<=1e5) Group example , Give each time n,m(1<=n,m<=1e5),

How many should be prepared at least for each inquiry Leadfoot badges, The answer is right 1e9+7 modulus

Source of ideas

Official explanation

Answer key

actually , There are enough drivers , The number of people equivalent to any step of the game is an integer ,

The solution to the question mentioned 2-adic valuation/kummer lemma, It sounds high-end , actually ,

2-adic valuation,2- Enter the assignment function , It can be considered as how many a number contains 2 The power of ,

Suppose the last game is to win , Then the front must have won n-1 game , And lost j site (0<=j<m), Consider the order ,C(n-1+j,j)

Suppose the last sentence is to lose , Empathy , The front lost m-1 game , Win. i site (0<=i<n), Consider the order ,C(m-1+i,i)

Suppose the number of drivers is 64（ contain 7 individual 2 The power of ）, And some final state C(n-1+j,j) The value of contains 3 individual 2 The power of （ Might as well be 8）,

Now , The number of drivers is 8, Terminal state C(n-1+j,j) The value of is 1, It is the optimal number of drivers corresponding to this final state ,

According to each final state , Find out the corresponding optimal number of drivers , The biggest one is The actual minimum number of drivers

Find out the minimum number of drivers , Divide 2 Of m Power , That is Continuous transportation m The minimum number of people in the field

actually , according to kummer Theorem ,

C(n+m,m) Include... Under binary 2 The power of , be equal to m+n Carry times of addition under binary ,

2e5 Insufficient binary bits of 20, The number of rounds will not exceed 20, Which contains 2 The power of cannot exceed 20,

therefore , Check only [max(0,i-20),i] and [max(0,j-20),j] that will do

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
#define dbg(x) cerr<<#x<<":"<<(x)<<endl;
int t,n,m,two[N];
int C(int n,int m){
    return two[n]-two[m]-two[n-m];
}
int modpow(int x,int n,int mod){
    int res=1;
    for(;n;n/=2,x=1ll*x*x%mod){
        if(n&1)res=1ll*res*x%mod;
    }
    return res;
}
int main(){
    for(int i=1;i<N;++i){
        for(int j=i;j%2==0;j/=2){
            two[i]++;
        }
        two[i]+=two[i-1];
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        int ans=0;
        for(int i=max(0,n-20);i<n;++i){
            for(int j=max(0,m-20);j<m;++j){
                ans=max(ans,1+i+j-C(i+j,i));
            }
        }
		//dbg(ans);
        printf("%d\n",modpow(2,ans-m,mod));
    }
    return 0;
}