TC502DIV1_1000

2016.03.29 20:08 Tue | 43次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给出n,要求从[1,n]中选出k个不同的数,使得这k个数的和是n的倍数,问方案数。
k<=1000,n<=1000000000

题解

dp

令f[i][j]表示从n中选出i个不同的数和是j的倍数的方案数。
现在,如果确定了前i-1个数,那么第i个数在模j意义下是唯一确定的,所以可以先让f[i][j]=C(n-1,i-1)*(n/j),n/j的意思是在模j意义下的解k可以变成k+j,k+2j...k+(n/j-1)j...
但是这样做会有两个数相同,对于这样的情况我们做以下处理:
假设我们把这两个数扔掉,那么剩下的数一定是gcd(2,j)的倍数
因为2x=b(mod p)的解只有b是gcd(p,2)的倍数时才存在,并且在模p意义下x的解有gcd(p,2)个。所以我们有
$f[i][j]=C_n^{i-1}(n/j)-f[i-2][gcd(2,j)]*gcd(j,2)(n/j)$
但是这样还是不对的,因为这步去掉的i和f[i-2][gcd(2,j)]中选择的数可能有重复的,所以还要继续容斥有3个数一样的情况。
同理,需要搞4,5,...,i个数相同的情况,最后的公式就变成了
$f_{i,j}=C_n^{i-1}(n/j)-\sum_{c=2}^i(-1)^cf_{i-c,gcd(c,j)}(n/j)gcd(j,c)$
算法的复杂度是k^2*n的约数个数。

mycode

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
int n,k;
int f[1005][2005];
int st[2005],top;
ll qpow(ll x,int k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%mod;
        k>>=1;x=x*x%mod;
    }
    return ret;
}
ll C(int n,int m)
{
    ll t1=1,t2=1;
    for(int i=1;i<=m;i++) t1=t1*(n+1-i)%mod,t2=t2*i%mod;
    return t1*qpow(t2,mod-2)%mod;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll calc(int i,int j)
{
    int k=lower_bound(st+1,st+top+1,j)-st;
    if(f[i][k]!=-1) return f[i][k];
    ll ret=C(n,i-1)*(n/j)%mod;
    for(int c=2;c<=i;c++) 
    {
        ll tmp=calc(i-c,gcd(j,c))*(n/j)%mod*gcd(j,c)%mod;
        (ret+=(c&1)?tmp:mod-tmp)%=mod;
    }
    ret=ret*qpow(i,mod-2)%mod;
    return f[i][k]=ret;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    if(n%i==0) st[++top]=i;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=top;i++) f[0][i]=1,f[1][i]=n/st[i];
    printf("%lld\n",calc(k,n));
}