反演+FFT+构造+DP
写了这么多tag，其实我一个也不会
A
第一题是反演……数据范围10W，看着就有种要用FFT等神奇算法的感觉……然而蒟蒻并不会推公式，只好写了20+10分的暴力，然而特判30分的时候好像挂了，所以并没有拿到……20分滚粗了
最近打暴力搞部分分的时候，写各种情况的判断条件什么的总是出问题……sad……以后还是自己造下数据判一下能不能过吧，不能总是靠人品啊>_>
我还是放弃FFT吧，反正……出来这种题，我也想不到要用FFT & 不会推公式……呵呵哒
//Round5 A
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,P=;
/*******************template********************/ LL n,b[N],a[N];
LL fac[N],inv[N];
LL Pow(LL a,int b){
LL r=;
for(;b;b>>=,a=a*a%P) if (b&) r=r*a%P;
return r;
} LL C(int n,int m){
return fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
n=getint();
if (n>){
F(i,,n) printf("1 "); puts(""); return ;
}
fac[]=fac[]=; F(i,,n) fac[i]=fac[i-]*i%P;
inv[n]=Pow(fac[n],P-); inv[]=;
D(i,n-,) inv[i]=inv[i+]*(i+)%P; F(i,,n) b[i]=getint();
bool sign=;
F(i,,n) if (b[i]!=C(n+,i+)){sign=; break;}
if (sign){F(i,,n) printf("1 "); puts(""); return ;}
D(i,n,){
F(j,i+,n) b[i]=((b[i]-C(j,i)*a[j]%P)+P)%P;
a[i]=b[i];
}
F(i,,n) printf("%lld ",b[i]); puts("");
return ;
}
B
qmqmqm神犇出的构造题，随便yy一下就可以联想到邻接矩阵，然后k次方后，a[i][j]就是从 i 开始走k步能否走到j。
然而我傻逼地没有特判k=1的情况
事实是：我在想到正解之前看到k=1的点发现这应该直接输出全1矩阵，再小一点的数据可以暴力枚举初始矩阵，然而……后来就没再像这种边界情况，真是作死。95分滚粗了
//Round5 B
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ int n,k;
struct Matrix{
bool c[N][N];
bool* operator [] (int x){return c[x];}
Matrix(){memset(c,,sizeof c);}
void print(){
// F(i,1,n){F(j,1,n) printf("%d ",c[i][j]); puts("");}
F(i,,n){
F(j,,n) printf("%c",c[i][j]+'');
puts("");
}
puts("");
}
}f; Matrix operator * (Matrix a,Matrix b){
Matrix c;
F(i,,n) F(k,,n) F(j,,n)
c[i][j]+=a[i][k]*b[k][j];
return c;
}
Matrix Pow(Matrix a,int b){
Matrix c;
F(i,,n) c[i][i]=;
for(;b;b>>=,a=a*a) if (b&) c=c*a;
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
n=getint(); k=getint();
if (k==){
F(i,,n){F(j,,n) printf("%c",''); puts("");}
return ;
}
F(i,,n) f[i][i]=; F(i,,k-) f[i][i+]=;
f[k][]=; F(i,k+,n) f[i][]=f[][i]=;
F(i,,n){
F(j,,n) printf("%c",f[i][j]+'');
puts("");
}
/* F(i,0,k){
printf("No. %d\n",i);
Pow(f,i).print();
}*/
return ;
}
C
对我来说神一样的DP，然而并不能找到一种合理的状态表示方式，所以也就搞不出来了……快速幂10分滚粗
//Round5 C
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,P=1e9+;
/*******************template********************/ int n,m,k;
LL f[N][N],fac[N],inv[N];
LL Pow(LL a,int b){
LL r=;
for(;b;b>>=,a=a*a%P) if (b&) r=r*a%P;
return r;
}
LL C(int n,int m){return fac[n]*inv[m]*inv[n-m]%P;} int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
n=getint(); m=getint(); k=getint();
fac[]=fac[]=;
F(i,,k) fac[i]=fac[i-]*i%P;
inv[k]=Pow(fac[k],P-); inv[]=;
D(i,k,) inv[i-]=inv[i]*i%P; if (n==){printf("%lld\n",Pow(k,m)); return ;}
else{
}
return ;
}
下午去考了信息会考，然后就回来改题……然而什么也不会，心情好糟糕，什么也不想做……整个人都不好了……
o(︶︿︶)o 唉还有35？还是34？天就要NOI了……我还是这么傻逼，没救了，是不是退OI保平安比较好……