【NOIP2014八校聯考第1場第2試9.21】大水題(water)

NO IMAGE

Description

dzy 定義一個n^2 位的數的生成矩陣A 為一個大小為n*n 且Aij 為這個數的第i*n j-n位的矩陣。
現在dzy 有一個數n^2 位的數k,他想知道所有小於等於k 的數的n*n 生成矩陣有多少種。(如果不足n^2 位則補字首零)

Solution

其實題意轉化一下就是在k裡面找到所有的要求的數的個數(如果翻轉過來也存在,那麼只算一次)
我們正難則反。
設f(i)為i在n2n^2位中翻轉後的數。
ans=k−∑f(i)∈[1,k]−∑f(i)=i2ans=k-{\sum f(i)∈[1,k]-\sum f(i)=i\over 2}
上面的式子很顯然,就是找出能翻轉的數的個數/2(除去迴文數)
那麼現在就是經典的數位DP的時間了。
設f[i][p][q]f[i][p][q]為,做完i位的時候,是否與k的前i位相等(肯定是≤),翻轉過來是否爆掉後i位,所以p和q是0,1狀態。
然後求出f之後。
ans=k−(f[n][1][1] f[n][0][1])−(f[n/2][1][0] f[n/2][1][1] f[n/2][0][1])2ans=k-{(f[n][1][1] f[n][0][1])-(f[n/2][1][0] f[n/2][1][1] f[n/2][0][1])\over 2}

Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i  )
using namespace std;
const int maxn=1007*1007,mo=1000000007;
typedef long long ll;
ll i,j,k,l,t,n,m,ans,x,y,er,dan;
ll a[maxn],f[maxn][2][2],b,c;
char s[maxn];
int main(){
er=500000004;
scanf("%lld",&n);n=n*n;
scanf("%s",s 1);
fo(i,1,n)a[i]=s[i]-'0',ans=(ans*10 a[i])%mo;
f[0][0][1]=1;
fo(i,0,n-1){
fo(j,0,1){
fo(k,0,1){
if(!f[i][j][k])continue;
fo(l,0,9){
if(j||a[i 1]>=l){
b=(a[i 1]>l)||j;
c=(a[n-i]>l)||(l==a[n-i]&&k);
(f[i 1][b][c] =f[i][j][k])%=mo;
}
}
}
}
}
dan=(f[n][0][1] f[n][1][1])%mo;
dan=(dan-f[n/2][1][1]-f[n/2][1][0]-f[n/2][0][1])%mo;
dan=dan*er%mo;
ans=((ans-dan)%mo mo)%mo;
printf("%lld\n",ans);
}