首页 > 代码库 > HDU 4810 这道题 是属于什么类型?
HDU 4810 这道题 是属于什么类型?
统计每一位出现1的个数 求组合数
直接贴代码
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <cstdlib>#include <ctime>#include <string>#define CL(a,b) memset(a,b,sizeof(a))#define INF 0x3fffffff#define MID int mid=(l+r)>>1;#define ll __int64using namespace std;const ll mod=1000003;ll power(ll a,ll b){ if(b==0)return 1; if(b==1)return a; ll rem=power(a,b/2); rem=(rem*rem)%mod; if(b%2==1) { rem*=a; rem%=mod; } return rem%mod;}ll ni(ll x){ return power(x,mod-2);}ll C[1010][1010];void initc(){ int i,j; for(i=0;i<=1005;i++) { C[i][0]=1; } for(i=1;i<=1005;i++) { for(j=1;j<=i;j++) { C[i][j]=C[i][j-1]*(i-j+1)*ni(j); C[i][j]%=mod; } }}ll val[80];int sum[80];void initval(){ int i; val[0]=1; for(i=1;i<80;i++) { val[i]=val[i-1]*2; val[i]=val[i]%mod; }}int main(){ int n,m; initc(); initval(); while(scanf("%d",&n)!=EOF) { int i,j,maj=0,k; CL(sum,0); ll rem,a; for(i=0;i<n;i++) { scanf("%I64d",&a); j=0; while(a) { sum[j]+=a%2; a/=2; j++; } if(maj<j-1)maj=j-1; } for(i=1;i<=n;i++) { rem=0; for(j=0;j<=maj;j++) { for(k=1;k<=i;k+=2) { if(!(k<=sum[j]&&i-k<=n-sum[j]))continue; rem+=(val[j]*C[sum[j]][k]*C[n-sum[j]][i-k])%mod; rem=rem%mod; } } if(i!=1)printf(" "); printf("%I64d",rem); } printf("\n"); } return 0;}
HDU 4810 这道题 是属于什么类型?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。