Chino with Equation 不定方程

￡神魔★判官ぃ 2022-09-10 01:26 35阅读 0赞

假设未知数m个

不定方程，用插板法来想，

求正整数解：m个桶，放n件东西，每个桶至少一件： C(n-1, m-1)

求非负数解：C(n+m-1, m-1)

看m和的数据范围，用什么方式求组合数

可以用费马小定理

// Problem: Chino with Equation
    // Contest: NowCoder
    // URL: https://ac.nowcoder.com/acm/contest/553/D
    // Memory Limit: 524288 MB
    // Time Limit: 2000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define ff first
    #define ss second
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b; i>=a; --i)
    typedef pair<int,int> PII;
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int inf=0x3f3f3f3f;
    const ll mod = 1e9 + 7;
    const int N=2e6+100;
    ll n, m;
    ll fac[N];
    vector<int> v(N);
    
    ll qmi(ll a, ll b)
    { 
    	ll res = 1;
    	while(b)
    	{ 
    		if(b&1) res = res * a % mod;
    		a = a * a % mod;
    		b>>=1;
    	}
    	return res;
    }
    
    void init()
    { 
    	fac[0] = 1;
    	for(ll i = 1; i < N; i ++ ) fac[i] = fac[i-1] * i % mod;
    }
    
    ll cal(ll n, ll m)
    { 
    	if(n < 0 or m < 0 or n < m) return 0;
    	ll ans = fac[n];
    	ans = ans * qmi(fac[m], mod-2) % mod;
    	ans = ans * qmi(fac[n-m] ,mod-2) % mod;
    	return ans;
    }
    
    void solve()
    { 
    	init();
    	cin >> m >> n;
    	cout << cal(n-1, m-1) << " " << cal(n+m-1, m-1) << endl;
    }
    
    int main()
    { 
    	ios::sync_with_stdio(false);cin.tie(0);
    	solve();
    	return 0;
    }