首页 > 代码库 > HDU4675-GCD of Sequence(数论+组合计数)
HDU4675-GCD of Sequence(数论+组合计数)
GCD of Sequence
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 949 Accepted Submission(s): 284
Problem Description
Alice is playing a game with Bob.
Alice shows N integers a1, a2, …, aN, and M, K. She says each integers 1 ≤ ai ≤ M.
And now Alice wants to ask for each d = 1 to M, how many different sequences b1, b2, …, bN. which satisfies :
1. For each i = 1…N, 1 ≤ b[i] ≤ M
2. gcd(b1, b2, …, bN) = d
3. There will be exactly K position i that ai != bi (1 ≤ i ≤ n)
Alice thinks that the answer will be too large. In order not to annoy Bob, she only wants to know the answer modulo 1000000007.Bob can not solve the problem. Now he asks you for HELP!
Notes: gcd(x1, x2, …, xn) is the greatest common divisor of x1, x2, …, xn
Alice shows N integers a1, a2, …, aN, and M, K. She says each integers 1 ≤ ai ≤ M.
And now Alice wants to ask for each d = 1 to M, how many different sequences b1, b2, …, bN. which satisfies :
1. For each i = 1…N, 1 ≤ b[i] ≤ M
2. gcd(b1, b2, …, bN) = d
3. There will be exactly K position i that ai != bi (1 ≤ i ≤ n)
Alice thinks that the answer will be too large. In order not to annoy Bob, she only wants to know the answer modulo 1000000007.Bob can not solve the problem. Now he asks you for HELP!
Notes: gcd(x1, x2, …, xn) is the greatest common divisor of x1, x2, …, xn
Input
The input contains several test cases, terminated by EOF.
The first line of each test contains three integers N, M, K. (1 ≤ N, M ≤ 300000, 1 ≤ K ≤ N)
The second line contains N integers: a1, a2, ..., an (1 ≤ ai ≤ M) which is original sequence.
The first line of each test contains three integers N, M, K. (1 ≤ N, M ≤ 300000, 1 ≤ K ≤ N)
The second line contains N integers: a1, a2, ..., an (1 ≤ ai ≤ M) which is original sequence.
Output
For each test contains 1 lines :
The line contains M integer, the i-th integer is the answer shows above when d is the i-th number.
The line contains M integer, the i-th integer is the answer shows above when d is the i-th number.
Sample Input
3 3 3 3 3 3 3 5 3 1 2 3
Sample Output
7 1 0 59 3 0 1 1HintIn the first test case : when d = 1, {b} can be : (1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 2) (2, 1, 1) (2, 1, 2) (2, 2, 1) when d = 2, {b} can be : (2, 2, 2) And because {b} must have exactly K number(s) different from {a}, so {b} can‘t be (3, 3, 3), so Answer = 0
题意:有n个数(n <= 10^5),每个数的小于等于M(M <=10^5)
现在让你求把原数列改变k个数,使新数列最大公约数为d (d为1~M)的方法数,分别输出
思路:这是一道非常不错的数论题,即使推出公式,一些细节上的优化如果做得不到位的话也会超时。
当最大公约数为d时,易得1~M中d的倍数有 M/d个,我们统计原数列中d的倍数的个数cnt,那么所先要将原数列中的非d得倍数的数变成d的倍数,这样的方案数一共有
(M/d)^(n-cnt) 然后还剩下k-(n-cnt) 个数需要变换,那么方案数为 C(cnt))(n-k)*(M/d-1)^(k-(n-cnt) )_ 那么总的为d的倍数的方案数为(M/d)^(n-cnt)*C(cnt))(n-k)*(M/d-1)^(k-(n-cnt) ) 此时,还需要减掉为i*d的倍数的方案数(因为最终答案要求的是最大公约数为d的方案数,而此时的算的是为d的倍数的方案数)
这时候先算好组合数,(因为组合数的第二个数是不变的,复杂度从M降为1)并统计好1~M每个数出现的次数(复杂度从n降为lgm),从m开始计算答案,这样复杂度为m*lgm。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> using namespace std; const int maxn = 300000+10; const int MOD = 1000000007; typedef long long ll; int n,m,k; int num[maxn]; ll Cot[maxn]; ll cnt[maxn]; ll ans[maxn]; inline void gcd(int a,int b,int& d,int &x,int &y){ if(!b){ d = a; x = 1;y = 0; }else{ gcd(b,a%b,d,y,x); y -= x*(a/b); } } inline ll inv(int a){ int d,x,y; gcd(a,MOD,d,x,y); return d == 1? (x+MOD)%MOD:-1; } inline ll pow_mod(int a,int b){ if(b < 0) return 0; if(a==1) return 1; ll ret = 1,pow = a; while(b){ if(b&1) ret = (ret*pow)%MOD; pow = (pow*pow)%MOD; b >>= 1; } return ret; } int main(){ while(~scanf("%d%d%d",&n,&m,&k)){ ll ret = 0; bool flag = true; memset(cnt,0,sizeof cnt); Cot[n-k] = 1; int tmp = n-k; for(int i = n-k+1; i <= n; i++){ Cot[i] = (Cot[i-1]*i)%MOD*inv(i-tmp)%MOD; } for(int i = 1; i <= n; i++){ scanf("%d",&num[i]); cnt[num[i]]++; } for(int i = m; i >= 1; i--){ int sum = cnt[i],che = 0; for(int j = i+i; j <= m; j += i){ sum += cnt[j]; che = (ans[j]+che)%MOD; } if(sum < tmp) ans[i] = 0; else{ int d = m/i; ans[i] = Cot[sum]*pow_mod(d-1,sum-tmp)%MOD*pow_mod(d,n-sum)%MOD; ans[i] = (ans[i]-che+MOD)%MOD; } } printf("%I64d",ans[1]); for(int i = 2; i <= m; i++){ printf(" %I64d",ans[i]); } printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。