题解 P1771 【方程的解_NOI导刊2010提高（01）】

荣一鸣 · 2018-07-07 19:54:06 · 题解

一看就是数论

知道是数论也不会做！！！

x^x%1000可以用快速幂做

没做过的可以走这里快速幂

所以就是关于将n分为k份并求求其全排列的问题，其实也就是从n个物品里取k个的组合数

说到这里相信就都明白了，公式就是n!/k!/(n-k)!

这里用高精度计算就行了

#include<iostream>
#include<cstdio>
using namespace std;
int k,x;
int mod=1000;
int a[10100];

int mulm(int a,int b){//快速模幂
    if(b==1) return a;
    int t=mulm(a,b>>1);
    t*=t;
    t%=mod;
    if(b%2==1){
        t*=a;
        t%=mod;
    }
    return t;
}

void comb(int n,int m){//求组合
    a[1]=1;
    a[0]=1;
    for(int i=m+1;i<=n;i++){
        for(int j=1;j<=a[0];j++){
            a[j]*=i;
        }
        int tmp=0;
        for(int j=1;j<=a[0];j++){
            tmp+=a[j];
            a[j]=tmp%10;
            tmp/=10;
        }
        while(tmp){
            a[++a[0]]=tmp%10;
            tmp/=10;
        }
    }
    for(int i=2;i<=n-m;i++){
        int tmp=0;
        for(int j=a[0];j>=1;j--){
            tmp*=10;
            tmp+=a[j];
            a[j]=0;
            if(tmp>i){
                a[j]=tmp/i;
                tmp%=i;
            }
        }
        while(a[a[0]]==0) a[0]--;
    }
}

int main(){
    cin>>k>>x>>mod;
    x%=mod;//别忘了先模一下，不然可能会炸
    x=mulm(x,x);
    comb(x-1,k-1);
    for(int i=a[0];i>=1;i--) cout<<a[i];
    return 0;
}