URAL1091. Tmutarakan Exams(容斥)

1091

容斥原理

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
int p[],g,f[],q[],o,vis[],pa[],n,kk;
#define LL long long
void init()
{
int i,j;
for(i = ; i < ; i++)
if(!f[i])
for(j = i+i ; j < ; j+=i)
f[j] = ;
for(i = ; i < ; i++)
if(!f[i])
p[++g] = i;
}
LL find(int num,int k)
{
if(num<k) return ;
int i,x=k;
LL s = ;
for(i = ; i <= k ; i++)
{
s*=num;
num--;
while(x>&&s%x==)
{
s/=x;
x--;
}
}
return s;
}
LL dfs(int k,int v,int a)
{
int i,j;
LL s=;
if(a==o+&&v==k)
{
for(i = ; i <= n ; i++)
{
for(j = ; j <= v ; j++)
if(i%pa[j]!=)
break;
if(j==v+)
s++;
}
s = find(s,kk);
return s;
}
if(a>o) return ;
pa[v+] = p[a];
s+=dfs(k,v+,a+);
s+=dfs(k,v,a+);
return s;
}
int main()
{
int i,j;
init();
cin>>kk>>n;
LL s=;
for(i = ; i <= g ; i++)
{
int num = ;
for(j = ; j <= n ; j++)
if(j%p[i]==)
num++;
if(num<kk) continue;
q[++o] = p[i];
s+=find(num,kk);
}
for(i = ; i <= o ; i++)
{
memset(vis,,sizeof(vis));
LL pp=dfs(i,,);
if(i%==)
s-=pp;
else
s+=pp;
}
if(s>=)
cout<<""<<endl;
else
cout<<s<<endl;
return ;
}
上一篇:实例介绍Cocos2d-x物理引擎:使用关节


下一篇:python 忽略警告