BZOJ3930: [CQOI2015] 선택
처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설마.. 그럼 반전해 봐..아니야...그럼 난 도대체 뭘 할 줄 알아......문제풀이를 보면 그럴 것 같아요.
이 문제는 방법이 매우 많은데 주로 두 가지 유형이 있는데 하나는 반전이다. Orz PoPoQQQμ 의 접두사와 처리구는 알아볼 수 없다. 또한 하나의 유형은 용척이다. 구간에서 n개를 선택한 것은 모두 같은 수가 아니기 때문에 쉽게 증명할 수 있는 결론이 있다. 그들의 gcd는 구간의 길이를 초과하지 않기 때문에 현재 구간을 (⌈l/K⌉r/K⌋)로 축소하고 f[i]를 설정하면 구간에서 n개를 선택한 것이 모두 같은 수가 아니라는 것을 의미한다. gcd는 i*K의 방안수이고 N은 선택할 수 있는 구간의 길이, 길이,하나의 공식 f[i]=Nn-3-N-3∑i|jf[j](N을 빼는 것은 똑같은 방안의 수를 모두 빼야 하기 때문) 마지막으로 똑같은 수를 모두 뽑아서 답안에 기여해야 한다. 그러면 K가 선택할 수 있는 구간에서만 1의 공헌이 발생한다.
code:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn = 100010;
const ll Mod = 1e9+7;
ll pw(ll x,int k)
{
x%=Mod;ll ret=1;
for(ll t=x;k;k>>=1,t=t*t%Mod)
if(k&1)ret=ret*t%Mod;
return ret;
}
ll f[maxn];
int n,K,L,H;
int main()
{
scanf("%d%d%d%d",&n,&K,&L,&H);
int l=L/K,r=H/K;
if(L%K) l++;
int N=r-l+1;
for(int i=N;i>=1;i--)
{
int tr=r/i,tl=l/i;
if(l%i)tl++;
if(tl<=tr)
{
f[i]=pw(tr-tl+1,n);
f[i]-=tr-tl+1;
for(int j=2*i;j<=N;j+=i) f[i]-=f[j];
f[i]=(f[i]%Mod+Mod)%Mod;
}
}
if(l<=1&&l<=r) f[1]=(f[1]+1)%Mod;
printf("%lld
",f[1]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3930: [CQOI2015] 선택거의 짠 물고기일 거야.. 처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.