낙곡P3750 [6개 성 연합고사 2017] 이별은 축원 dp

1872 단어 DP
제목:https://www.luogu.org/problemnew/show/P3750
분석: 분명히 스위치를 누르면 그보다 큰 수를 꺼뜨릴 수 없다.그래서 최선의 방안은 매번 가장 큰 수를 뽑아서 눌러야 한다.일괄 배수를 사용한 다음에vector로 어떤 수의 약수를 저장하여 눌러야 할 스위치 수 cn t cnt cnt를 구할 수 있습니다.f[i] f[i] f[i]는 ii개의 스위치를 누르고 iii-1i-1i-1i-1i-1 1개의 스위치를 누를 경우 몇 걸음이 필요한지, f[i] = i n + n - n - in (f[i+1] + f [i] + 1) f [i] + 1) f [i] =\rac {n} {n} + {n} + {n} {n} * (f[i+1] + f[i] + 1) f[i] + [i] + 1] + i [i] + 1] + 1) f[i] + i] + i[[i] + i] + i] + i] + i[[i] + nnnnn(i] + i] [i] + i] [[i] + i] + 눌러야 할 스위치가 도착하면 뒤에 눌러지지 않았다는 뜻입니다.그러면 i+1 i+1 i+1 스위치를 누르면 ii로 이동하고, ii에서 i-3-1 i-1 i-3-1로 이동해야 한다.그 중에서 f[n]=1 f[n]=1 f[n]=1, 만약 i <=k i<=k i<=k, f[i]=1 f[i]=1 f[i]=1 f[i]=1.정답은 ∑i = 1 c n t f [i]\sum{i=1}^{cnt}f[i] ∑i=1cnt​f[i].
코드:
// luogu-judger-enable-o2
#include 
#include 
#include 
#include 
#define LL long long

const int maxn=1e5+7;
const LL mod=100003;

using namespace std;

int n,k,cnt;
int a[maxn];
LL f[maxn],ans;

vector  p[maxn];

LL ksm(LL x,LL y)
{
    if (y==1) return x;
    LL c=ksm(x,y/2);
    c=c*c%mod;
    if (y&1) c=c*x%mod;
    return c;
}

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
    {
        for (int j=i;j<=n;j+=i)
        {
            p[j].push_back(i);
        }
    }
    for (int i=n;i>0;i--)
    {
        if (a[i])
        {
            cnt++;
            for (int j=0;j

0;i--) { f[i]=(f[i+1]*(LL)(n-i)+(LL)n)%mod*ksm(i,mod-2)%mod; } if (cnt<=k) ans=cnt; else { for (int i=k+1;i<=cnt;i++) ans=(ans+f[i])%mod; ans=(ans+k)%mod; } for (int i=1;i<=n;i++) ans=ans*(LL)i%mod; printf("%lld
",ans); }

좋은 웹페이지 즐겨찾기