梦.:如此短暂

SGU137 解题手记
　　设有n个元素，其和为k的数列为S(n,k)。则S(n,mn+k)容易求得，将S(n,k)的每个元素加上m即可。
　　S(n+mk,k)可以像这样由S(n,k)转化得来：
　　若S(n,k)[i]=r，则将其写成0 [0..0(m-1个) 1 ]..[0..0(m-1个) 1 ](r个)，例如 S(2,5)=2 3，则S(17,5)=0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1
　　要求S(N,K)，若K>N，则先求S(N,K%N)；若K<N，则先求S(N%K,K)。S(n,1)就是0...01。
　　辗转相除的过程是logn，总复杂度为O(nlogn)。
　　当K<N时，可以直接构造出01数列。设这个数列为f，与它同构的数列为g。则：
　　f[1]=0,f[N]=1
　　g[1]=1,g[N]=0
　　g[2..N-1]=f[2..N-1]
　　存在k，使 g[1..N]=f[k+1..N]+f[1..k]
　　即，在mod N的代数中：1=g[1]=f[k+1]=g[k+1]=f[2k+1]=g[2k+1]=...(pk≠N-1 (mod N) )
　　做完这个迭代过程，f数列里有p个位置就可以确定为1，题目要求要有K个位置为1，所以令p=K，把k求出来就行了（解Kk=N-1(mod N) ）。
　　Submit 1: AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <cstdio>
using namespace std;
 
int main()
{
    int n,K,Kt,k=1;
    int s[1000]={1};
    scanf("%d%d",&n,&K);
    Kt=K%n;
    while ((Kt*k+1)%n) k++;
    for (int i=1;(i*k+1)%n;i++) s[(i*k+1)%n]=1;
    for (int i=1;i<n;i++) printf("%d ",s[i]+K/n);
    printf("%d\n",s[0]+K/n);
    return 0;
}