清北NOIP训练营内部训练题

 

题目描述

LYK喜欢字符串，它认为一个长度为n的字符串一定会有n*(n+1)/2个子串，但是这些子串是不一定全部都不同的，也就是说，不相同的子串可能没有那么多个。LYK认为，两个字符串不同当且仅当它们的长度不同或者某一位上的字符不同。LYK想知道，在字符集大小为k的情况下，有多少种长度为n的字符串，且该字符串共有m个不相同的子串。

由于答案可能很大，你只需输出答案对1e9+7取模后的结果即可。

 

输入格式(string.in)

一行3个数n,m,k。

 

输出格式(string.out)

    一行，表示方案总数。

 

输入样例

2 3 3

 

输出样例

6

 

样例解释

共有6种可能，分别是ab,ac,ba,bc,ca,cb。

 

数据范围

对于20%的数据：1<><>

对于40%的数据：1<><><><>

对于60%的数据：1<><><><>

对于100%的数据：1<><><><><><>

 

Hint

本题非常easy。解析在标程之后。

#include

#include

using namespace std;

typedef long long LL;

const int mod=1e9+7;

int n,m;

int a[11];

LL has[11],b[11];

int f[11]; 

int inv[11];

LL Pow(LL a,int b)

{

    LL res=1;

    for(;b;a*=a,b>>=1)

        if(b&1) res*=a;

    return res;

}

void dfs(int now,int cnt,int lim)

{

    if(cnt>lim || n-now+1

    if(now==n+1)

    {

        for(int i=1;i<=n;++i) has[i]="">

        int sum=0;

        for(int len=1;len<>

        {

            for(int i=1;i+len-1<=n;++i) b[i]="">

            sort(b+1,b+n+1-len+1);

            for(int i=1;i+len-1<=n;++i) if(b[i]!="b[i-1])">

        }

        if(sum==m) f[lim]++;

        return;

    }

    for(int i=1;i<=cnt;++i) a[now]="">

    a[now]=cnt+1; dfs(now+1,cnt+1,lim);

}

int getC(int x,int y)

{

    int sum=1;

    for(int i=x-y+1;i<=x;++i) sum="">

    for(int i=1;i<=y;++i) sum="">

    return sum;

}

int pow(int a,int b)

{

    int res=1;

    for(;b;a=1LL*a*a%mod,b>>=1)

        if(b&1) res=1LL*res*a%mod;

    return res;

}

int main()

{

    freopen('string.in','r',stdin);

    freopen('string.out','w',stdout); 

    int k;

    scanf('%d%d%d',&n,&m,&k);

    int t=min(n,k);

    for(int i=1;i<=t;++i)>

    LL bit=1;

    for(int i=1;i<>

    {

        inv[i]=pow(i,mod-2);

        bit*=i;

        f[i]=f[i]*bit%mod;

    }

    int ans=0;

    for(int i=1;i<=t;++i) ans="">

    printf('%d',ans);