A - Nim or not Nim?
HDU - 3032
nim博弈，先占坑
B - Number Sequence
题目
给定b数列，求有几种a数列能使得a 1a 2...a n=b 1b 2…b n (a i>1)（bi<1e6, b 1b 2…*b n<=1e25)
思路
- 将b质因数分解，有pi个质因数p，放入n个位置中，可以有空位，则其组合数为c(n+p-1,n-1)。总的个数为所有质因数组合数。
- 上述结果包含有空位置的情况，因此需要容斥空位置
代码
分解质因数
void getFactors(long long x) {
long long tmp=x;
for(int i=2;i<=tmp/i;i++) {
if(tmp%i==0){
while(tmp%i==0){
mp[i]++;//把所有数的质因子都加入map中
tmp/=i;
}
} }
if(tmp!=1) {
mp[tmp]++;
}
}
组合数预处理
void init(){
for(int j=0;j<50;j++)
c[0][j]=1;
for(int i=1;i<50;i++)
for(int j=0;j<50;j++)
{
if(i==j) c[i][j]=1;
else if(j<i) c[i][j]=0;
else c[i][j]=(c[i-1][j-1]+c[i][j-1])%mod;
}
}
计数和容斥部分
ll ans=0;
map<ll,ll>::iterator it;
for(int i=1;i<=n;i++){
ll cnt=c[i-1][n];/*容斥n个里面少选了i个的总数，
初始值为选i个的组合数*/
for(it=mp.begin();it!=mp.end();it++){
ll x=it->second;
cnt=(cnt*c[n-i][x+n-i])%mod;
}
if(i%2) ans=(ans+cnt)%mod;
else ans=(ans-cnt+mod)%mod;
}
G - How Many Answers Are Wrong
HDU - 3038
tag：带权并查集
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2*1e5+100;
int fa[N];
int rnk[N];
void Init(int n)
{
for(int i=0;i<=n;i++)
{
fa[i]=i;
rnk[i]=0;
}
}
int Find(int x)
{
if(x==fa[x])return x;
int temp=fa[x];
fa[x]=Find(fa[x]);
rnk[x]=rnk[x]+rnk[temp];
return fa[x];
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2){
Init(n+1);
int cnt=0;
for(int i=1;i<=m;i++){
int u,v;
int k;
scanf("%d%d%d",&u,&v,&k);
v++;
int ru=Find(u);
int rv=Find(v);
if(ru!=rv) {
fa[ru]=rv;
rnk[ru]=k-rnk[u]+rnk[v];
}
else
{
if((-rnk[v]+rnk[u])!=k) {cnt++;}
}
}
printf("%d\n",cnt);
}
return 0;
}
I - Beautiful numbers
tag: 数位dp
题目
求l，r之间可以被所有非零位整除的数字个数。（l,r<=1e18）
思路
- dp[pos][shu][lcm];//第pos位，数为shu%2520，所有数位的lcm
- 2520为1-9所有数位的lcm
- 第三维需要hash一下，所有lcm的组合情况只有48种。
- 剩下的模板问题了。
代码
ll dfs(int pos,int premod,int prelcm,bool flag){
if(pos==0) return premod%prelcm==0;
if(flag&&~dp[pos][premod][h[prelcm]])
return dp[pos][premod][h[prelcm]];
int u=flag?9:bit[pos];
ll ans=0;
int nextmod,nextlcm;
for(int d=0;d<=u;d++){
nextmod=(premod*10+d)%mod;
nextlcm=prelcm;
if(d) nextlcm=lcm(prelcm,d);
ans+=dfs(pos-1,nextmod,nextlcm,flag||d<u);
}
if(flag) dp[pos][premod][h[prelcm]]=ans;
return ans;
}
M - The Lottery
tag：容斥原理
题目
求1~n中不能被给定m个数中任意一个数整除的数的个数
思路
直接代码吧
ll num=0;
for(int i=1;i<(1<<m);i++){
ll ans=1;int ant=0;
for(int j=0;j<m;j++){
if(i&(1<<j)){
ans=lcm(ans,a[j]);
ant++;
}
}
if((ant-1)%2) num-=(n/ans);
else num+=(n/ans);
}
cout<<n-num<<endl;
