zcmimi's blog
查看原题

点击跳转

\sum_{i=1}^k a_i = x^x \mod 1000 (a_i \in \N^*)

\because 总和一定为x^x \mod 1000,并且分为k个数,

n = x^x \mod 1000

这样相当于在n-1个空位中插k-1块隔板

\therefore ans = C(n-1,k-1)

\because k \le 100,n\le 1000

\therefore我们用杨辉三角(用滚动数组,否则可能re)就可以了,但是要高精度

当然如果直接计算组合数更快

杨辉三角版:

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){clr(ch,0);if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}IN& operator>>(string& ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;ch+=c;while((c=gc())!=EOF&&!isspace(c))ch+=c;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(string s){for(int i=0;s[i];i++)pt(s[i]);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 1011
int k,t;
il int pw(int x,int p){
    int ans=1;
    while(p){
        if(p&1)ans=1ll*ans*x%1000;
        p>>=1;x=1ll*x*x%1000;
    }
    return ans;
}
#define M 1000
struct node{
    node(){clr(a,0);len=0;};
    unsigned short a[M],len;
    void operator = (int x){
        while(x){
            a[++len]=x%10;
            x/=10;
        }
        reverse(a+1,a+len+1);
    }
    il void op(){
        Fdr(i,len,1)out<<a[i];
        out<<ln;
    }
}c[2][101];
node operator + (node a,node b){
    node c;
    int len=MAX(a.len,b.len);
    Fur(i,1,len)
        c.a[i]=a.a[i]+b.a[i];
    Fur(i,1,len-1)
        if(c.a[i]>9)c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
    while(c.a[len]>9){
        c.a[len+1]+=c.a[len]/10;
        c.a[len]%=10;
        ++len;
    }
    c.len=len;
    return c;
}
void work(int n,int m){
    c[0][0]=1;
    c[1][0]=1;
    Fur(i,1,n)
        Fur(j,1,m)
        c[i&1][j]=c[!(i&1)][j-1]+c[!(i&1)][j];
    c[n&1][m].op();
}
int main(){
    in>>k>>t;t%=1000;
    t=pw(t,t);
    work(t-1,k-1);
}

组合数版:

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i=x;i<=y;++i)
#define Fdr(i,x,y) for(int i=x;i>=y;--i)
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){clr(ch,0);if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}IN& operator>>(string& ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;ch+=c;while((c=gc())!=EOF&&!isspace(c))ch+=c;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(string s){for(int i=0;s[i];i++)pt(s[i]);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 1011
int k,t;
il int pw(int x,int p){
    int ans=1;
    while(p){
        if(p&1)ans=1ll*ans*x%1000;
        p>>=1;x=1ll*x*x%1000;
    }
    return ans;
}
int len=1,c[1000];
void work(int n,int m){
    len=1;c[1]=1;
    Fur(t,1,m){
        Fur(i,1,len)c[i]*=(n-t+1);
        Fur(i,1,len-1)c[i+1]+=c[i]/10,c[i]%=10;
        while(c[len]>9)c[len+1]+=c[len]/10,c[len]%=10,++len;

        int y=0;
        Fdr(i,len,1){
            y=y*10+c[i];
            c[i]=y/t,y%=t;
        }
        while(!c[len]&&len>1)--len;
    }
    Fdr(i,len,1)out<<c[i];out<<ln;
}
int main(){
    in>>k>>t;t%=1000;
    t=pw(t,t);
    work(t-1,k-1);
}
LG 1771 方程的解_NOI导刊2010提高(01)
comment评论
Search
search