题目链接
vjudge TheCowDivOne Topcoder 11351 TheCowDivOne
题目大意
有一个大小为 (N) 集合 ({0,1,...,N-1}),求它有多少个大小为 (K) 的子集满足元素和为 (N) 的倍数。
(1leq Nleq 10^9), (1leq Kleq 1000),答案对 (10^9+7) 取模。
思路
由于原来的这个集合是模 (N) 的一个完全剩余系,如果我们允许重复,那么前 (K-1) 个元素可以随便选择,最后一个元素根据目前模 (N) 的数值确定一下即可。题目要求不能重复,于是考虑容斥。
设 (f_{i,s}) 为「和为 (s) 的大小为 (i) 的子集」的数量,根据容斥,我们转移时枚举下一个数字被重复使用了几次,设当前是使用了 (j) 次,显然这个数字重复 (j) 遍只能产生模意义下 (gcd(j,s)) 的任意倍数(裴蜀定理),这要求上一个状态,即之前 (i-j) 个数的和已经为 (gcd(j,s)) 的倍数,才能凑齐 (s) 。而在模 (s) 下,共有 (gcd(j,s)) 个可行解(裴蜀定理的通解形式),由于数值范围是 ([0,N-1]),从而一共有 (frac{N}{s}gcd(j,s)) 个可行的数字。于是便可以得到转移式:
前面的 (frac{1}{i}) 是由于 (i) 个数字每一个都可能成为最后那个选的数字,所以要去重。
这个 (dp) 的第二维只涉及到 (N) 的所有因数,这个转移,emmm,总之就是状态数实际上很少。实测下来,当 (N=12! imes2approx 9.58e8),(K=1000) 时,计算到的 (i>0) 的状态数为 (4478),(gcd) 内的运算量为 (15219724) 。这个数量很少,我们用记忆化搜索计算 (dp) 即可。
时间复杂度:(O(不会算))
Code
#include<iostream>
#include<map>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 1021
#define mod 1000000007
#define ll long long
using namespace std;
map<int, ll> dp[N];
class TheCowDivOne{
public:
int n, k;
int gcd(int a, int b){ return b ? gcd(b, a%b) : a; }
ll qpow(ll a, int b){
ll ret = 1;
for(; b; b >>= 1){ if(b&1) (ret *= a) %= mod; (a *= a) %= mod; }
return ret;
}
ll solve(int i, int s){
if(i == 0) return 1;
if(dp[i].count(s)) return dp[i][s];
dp[i][s] = 0;
rep(j,1,i) (dp[i][s] += ((j&1) ? 1 : -1) * gcd(j, s) * solve(i-j, gcd(j, s)) % mod) %= mod;
(dp[i][s] *= (ll)n/s * qpow(i, mod-2) % mod) %= mod;
return dp[i][s];
}
int find(int _n, int _k){
n = _n, k = _k;
return int(solve(k, n)+mod)%mod;
}
} solve;
int main(){
int n, k;
cin>>n>>k;
cout<< solve.find(n, k) <<endl;
return 0;
}