题解 P1771 【方程的解_NOI导刊2010提高（01）】
localhost
·
·
题解
\sum_{i=1}^k a_i = x^x \mod 1000 (a_i \in \N^*)
设$n = x^x \mod 1000
这样相当于在n-1个空位中插k-1块隔板
\therefore ans = C(n-1,k-1)
\because k \le 100,n\le 1000
当然如果直接计算组合数更快
杨辉三角版:
```cpp
#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);
}
```
组合数版：
```cpp
#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);
}
```