LG P4161 [SCOI2009]遊戲/LG P6280 [USACO20OPEN]Exercise G

2020 年 8 月 23 日
筆記
DP, luogu, 數學

Description(P4161)

windy學會了一種遊戲。

對於1到N這N個數字，都有唯一且不同的1到N的數字與之對應。

最開始windy把數字按順序1，2，3，……，N寫一排在紙上。

然後再在這一排下面寫上它們對應的數字。

然後又在新的一排下面寫上它們對應的數字。

如此反覆，直到序列再次變為1，2，3，……，N。

如： 1 2 3 4 5 6

對應的關係為

1->2 2->3 3->1 4->5 5->4 6->6

windy的操作如下

1 2 3 4 5 6

2 3 1 5 4 6

3 1 2 4 5 6

1 2 3 5 4 6

2 3 1 4 5 6

3 1 2 5 4 6

1 2 3 4 5 6

這時，我們就有若干排1到N的排列，上例中有7排。

現在windy想知道，對於所有可能的對應關係，有多少種可能的排數。

Description(P6280)

Farmer John（又）想到了一個新的奶牛晨練方案！
如同之前，Farmer John 的 $N$ $頭奶牛站成一排。對於$1\leq i \leq N$的每一個 $i$，從左往右第 $i$ 頭奶牛的編號為 $i$。他告訴她們重複以下步驟，直到奶牛們與她們開始時的順序相同。$

給定長為 $N$ $$A_i$ 頭。例如，如果 $A=(1,2,3,4,5)$，那麼奶牛們總共進行一步。如果 $A=(2,3,1,5,4)$，那麼奶牛們總共進行六步。每步之後奶牛們從左往右的順序如下：$

0 步：$(1,2,3,4,5)$

由於這個數字可能非常大，輸出答案模 $M$ $的餘數（$10^8 \leq M \leq 10^9+7$，$M$ 是質數）。$

$設$f_{i,j}$表示在前$i$個質數中，拆分數$j$所能得到的$lcm$個數/和$

$f_{i,j}=\sum_{k=0}^{j\geq p_{i}^k} dp_{i-1,j-p_{i}^k}$

$f_{i,j}=\sum_{k=0}^{j\geq p_{i}^k} dp_{i-1,j-p_{i}^k}\times p_{i}^k$

#include<iostream>
#include<cstdio>
using namespace std;
int n,tot,prime[1005];
long long dp[1005],ans;
bool vst[1005];
inline int read()
{
    int w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return w*f;
}
int main()
{
    n=read();
    for(int i=2;i<=n;i++)
    {
        if(!vst[i])
        {
            prime[++tot]=i;
        }
        for(int j=1;j<=tot&&prime[j]*i<=n;j++)
        {
            vst[prime[j]*i]=true;
            if(!(i%prime[j]))
            {
                break;
            }
        }
    }
    dp[0]=1;
    for(int i=1;i<=tot;i++)
    {
        for(int j=n;j>=prime[i];j--)
        {
            int temp=prime[i];
            while(j>=temp)
            {
                dp[j]+=dp[j-temp];
                temp*=prime[i];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans+=dp[i]; 
    }
    printf("%lld\n",ans+1);
    return 0;
}

遊戲

#include<iostream>
#include<cstdio>
using namespace std;
long long n,tot,prime[10005],mod;
long long dp[10005],ans;
bool vst[10005];
inline long long read()
{
    long long w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return w*f;
}
int main()
{
    n=read();
    mod=read();
    for(long long i=2;i<=n;i++)
    {
        if(!vst[i])
        {
            prime[++tot]=i;
        }
        for(long long j=1;j<=tot&&prime[j]*i<=n;j++)
        {
            vst[prime[j]*i]=true;
            if(!(i%prime[j]))
            {
                break;
            }
        }
    }
    dp[0]=1;
    for(long long i=1;i<=tot;i++)
    {
        for(long long j=n;j>=prime[i];j--)
        {
            long long temp=prime[i];
            while(j>=temp)
            {
                (dp[j]+=dp[j-temp]*temp)%=mod;
                temp*=prime[i];
            }
        }
    }
    for(long long i=1;i<=n;i++)
    {
        (ans+=dp[i])%mod;
    }
    printf("%lld\n",(ans+1)%mod);
    return 0;
}

Exercise G

Tags: DP luogu 數學